You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

失忆的 Eden 总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。

记忆中，她总是喜欢给 Eden 出谜题：在 valentine's day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden 这样的一个问题：有 $n$ 个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱 $m$ 固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过 $m$，且价值和最大。

众所周知的，这是一个很经典的多重背包问题，Eden 很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。

这下 Eden 犯难了，不过 Eden 不希望自己被难住，你能帮帮他么？

输入格式

第一行有一个整数，代表玩偶的个数 $n$，玩偶从 $0$ 开始编号。

第二行开始后面的 $n$ 行，每行三个整数，第 $(i + 2)$ 行的整数 $a_i, b_i, c_i$，分别表示买一个第 $i$ 个玩偶需要的价钱，获得的价值以及第 $i$ 个玩偶的限购次数。

接下来的一行有一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个整数 $d_i, e_i$，表示每个询问去掉的是哪个玩偶（注意玩偶从 $0$ 开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立）。

输出格式

输出 $q$ 行，第 $i$ 行输出对于第 $i$ 个询问的答案。

5 
2 3 4 
1 2 1 
4 1 2 
2 1 1 
3 2 3 
5 
1 10 
2 7 
3 4 
4 8 
0 5

13 
11 
6 
12 
4

说明/提示

样例解释

一共五种玩偶，分别的价钱价值和限购次数为 $(2,3,4)$， $(1,2,1)$， $(4,1,2)$， $(2,1,1)$， $(3,2,3)$。

五个询问，以第一个询问为例。

第一个询问表示的是去掉编号为 $1$ 的玩偶， 且拥有的钱数为 $10$ 时可以获得的最大价值，则此时剩余玩偶为 $(2,3,4$)，$(4,1,2)$， $(2,1,1)$，$(3,2,3)$，若把编号为 $0$ 的玩偶买 $4$ 个（即全买了），然后编号为 $3$ 的玩偶 买一个，则刚好把 $10$ 元全部花完，且总价值为 $13$。可以证明没有更优的方案了。

注意买某种玩偶不一定要买光。

数据规模与约定

• 对于 $10\%$ 的数据，保证 $n \leq 10$。
• 另外存在 $20\%$ 的数据，保证 $n \leq 100$，$c_i = 1$，$q \leq 100$。
• 另外存在 $20\%$ 的数据，保证 $n \leq 100$，$q \leq 100$。
• 另外存在 $30\%$ 的数据，保证 $c_i = 1$。
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 1000$，$1 \leq q \leq 3\times 10^5$， $1 \leq a_i,b_i,c_i \leq 100$，$0 \leq d_i < n$，$0 \leq e_i \leq 1000$。