Comet OJ

C1488 [HEOI2013]Eden的新背包问题

内存限制：256 MB 时间限制：1000 ms

题目描述

“寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心心静，能不能说给我听。”失忆的 Eden 总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。

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

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

输入格式

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

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

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

输出

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

样例

样例输入 1

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

样例输出 1

13
11
6
12
4

提示

$100\%$ 数据满足 $1 ≤ n ≤ 1000, 1 ≤ q ≤ 3 \times 10^5 , 1 ≤ a_i、b_i、c_i ≤ 100, 0 ≤ d_i < n, 0 ≤e_i ≤ 1000$。