[HEOI2013] Eden 的新背包问题
题目背景
“ 寄 没 有 地 址 的 信 ,这 样 的 情 绪 有 种 距 离 ,你 放 着 谁 的 歌 曲 ,是 怎 样 的 心 情 。 能 不 能 说 给 我 听 。”
题目描述
失忆的 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$ 个询问的答案。
输入输出样例
输入样例 #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
说明
#### 样例解释
一共五种玩偶,分别的价钱价值和限购次数为 $(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$。