Eden's Memory: Multi-Pack Knapsack Puzzle

Eden, who suffers from amnesia, struggles to recall her past. In her memories, she recalls a special moment on Valentine's Day when she was challenged with a puzzle involving a collection of exquisite dolls. Each doll has an associated value, cost, and a limited number of copies available for purchase. The problem is to select some dolls, buying a limited number of each, such that the total cost does not exceed a given budget and the total value is maximized.

Formally, you are given \( n \) dolls. For the \( i\text{-th} \) doll, you are provided with its value \( v_i \), cost \( c_i \), and the maximum quantity \( k_i \) available. Initially, you consider all dolls. Then, there are \( Q \) queries. In each query, you are given a new total money \( M \) and an index \( r \) indicating a doll that is removed (and can no longer be chosen). For each query, compute the maximum total value obtainable by selecting dolls (adhering to each doll's quantity limit) among those remaining while keeping the total cost \( \le M \).

This is a classic multi-pack knapsack problem with a twist: every query removes one doll and provides a different budget.

inputFormat

The first line contains two integers \( n \) and \( Q \) — the number of dolls and the number of queries.

Each of the next \( n \) lines contains three integers \( v_i \), \( c_i \), and \( k_i \) describing the value, cost, and maximum available quantity of the \( i\text{-th} \) doll.

Then, each of the next \( Q \) lines contains two integers \( M \) and \( r \), where \( M \) is the total money available in that query and \( r \) (1-indexed) is the doll that is removed.

outputFormat

For each query, output a single integer on a new line — the maximum total value obtainable under the given conditions.

sample

3 3
10 5 2
20 10 1
15 7 3
20 2
15 1
25 3

40
30
40