Description

The amnesiac Eden keeps trying to recall the past, yet he can only clearly remember the feeling of longing, not her face or smile.

In his memory, she always liked giving Eden puzzles. On Valentine's Day night, while the two were strolling through a bustling street and gazing at the delicate dolls in a gift shop, she suddenly asked Eden a question: there are $n$ dolls. Each doll has a cost and a value, and each doll can be bought a limited number of times. With a fixed budget $m$, how should one choose which dolls to buy and how many copies of each, so that the total cost does not exceed $m$ and the total value is maximized.

As is well known, this is a classic multiple knapsack problem. Eden solved it quickly, but she seemed a bit unhappy that her problem was answered so fast. So she made it harder: there will be multiple queries. In each query, a new budget is given and one doll is removed (i.e., that doll cannot be chosen). Then the answer to the multiple knapsack under this condition is asked (i.e., the problem described above).

Now Eden is in trouble, but he does not want to be stumped. Can you help him?.

Input Format

• The first line contains an integer $n$, the number of dolls. Dolls are indexed starting from $0$.
• The next $n$ lines, each line contains three integers. On line $i + 2$, the integers $a_i, b_i, c_i$ denote the cost of one copy of doll $i$, the value obtained, and the purchase limit of doll $i$, respectively.
• The next line contains an integer $q$, the number of queries.
• The next $q$ lines, each contains two integers $d_i, e_i$, indicating which doll is removed (note that dolls are indexed from $0$) and the new budget for this query. The removal does not persist, i.e., different queries are independent.

Output Format

Output $q$ lines. On the $i$-th line, output the answer for the $i$-th query.

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 

Hint

Sample Explanation.

There are five types of dolls. Their costs, values, and purchase limits are $(2,3,4)$, $(1,2,1)$, $(4,1,2)$, $(2,1,1)$, $(3,2,3)$.

There are five queries. Take the first query as an example.

The first query removes the doll with index $1$, and asks for the maximum value when the budget is $10$. The remaining dolls are $(2,3,4)$, $(4,1,2)$, $(2,1,1)$, $(3,2,3)$. If you buy $4$ copies of doll $0$ (i.e., all of them), and then buy one copy of doll $3$, you spend exactly $10$ and the total value is $13$. It can be proved that there is no better solution.

Note that you do not have to buy all available copies of a doll.

Constraints.

• For $10\%$ of the testdata, it is guaranteed that $n \leq 10$.
• Additionally, for $20\%$ of the testdata, it is guaranteed that $n \leq 100$, $c_i = 1$, $q \leq 100$.
• Additionally, for $20\%$ of the testdata, it is guaranteed that $n \leq 100$, $q \leq 100$.
• Additionally, for $30\%$ of the testdata, it is guaranteed that $c_i = 1$.
• For $100\%$ of the testdata, it is guaranteed that $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$.

Translated by ChatGPT 5