题目背景

一年一度的卡尔-玛卡巴卡杯开始了!

题目描述

卡尔-玛卡巴卡杯有 $n$ 个题目。对于每一道题目，你可以选择消耗 $w$ 点智力解决；或者寻求 AI 帮助，消耗 $c$ 点

$tokens$ 解决。无论通过哪种方式解决题目，你都会获得 $v$ 点得分。

现在给定 $q$ 个询问，每个询问给出你的智力值 $x$ 和 $tokens$ 值 $y$ 。你需要计算：在智力消耗总和不超过 $x$，$tokens$

消耗总和不超过 $y$ 的前提下，最多可以获得多少得分。每次询问独立。

注意：对于每个题目，你只需要选择一种方式解决（使用智力或使用 $tokens$），也可以选择不解决该题目。

输入格式

每个测试文件包含单组测试数据。

第一行一个整数 $n$（$1 \le n \le 1000$），表示题目的数量。

接下来 $n$ 行，每行包含三个整数 $w_i$ , $c_i$ , $v_i$ $(1 \le w_i, c_i, v_i \le 100)$，分别表示解决第 $i$ 个题目所需的智力值、所

需的 $tokens$ 值以及可以获得的得分。

接下来一行包含一个整数 $q$ $(1 \le q \le 10^4)$，表示询问的数量。

接下来 $q$ 行，每行包含两个整数 $x_j$, $y_j$ $(0 \le x_j , y_j \le 100)$，表示第 $j$ 个询问的智力值和 $tokens$ 值。

输出格式

对于每个询问，输出一行一个整数，表示在该智力值和 $tokens$ 值的限制下，能够获得的最大得分。

2
1 1 10
1 1 1
3
1 1
0 1
1 0

11
10
10