A9690 | New Year Shopping

Dohyun is running a grocery store. He sells $n$ items numbered by integers from 1 to $n$ . The $i$ -th ( $1<=i<=n$ ) of them costs $c_{i}$ dollars, and if I buy it, my happiness increases by $h_{i}$ . Each item can be displayed only for $p$ units of time because of freshness. As Dohyun displays the $i$ -th item at time $t_{i}$ , the customers can buy the $i$ -th item only from time $t_{i}$ to time $t_{i}+(p-1)$ inclusively. Also, each customer cannot buy the same item more than once.

I'd like to visit Dohyun's grocery store and buy some items for the New Year Party, and maximize my happiness. Because I am a really busy person, I can visit the store only once, and for very short period of time. In other words, if I visit the store at time $t$ , I can only buy the items available at time $t$ . But I can buy as many items as possible, if the budget holds. I can't buy same item several times due to store rules. It is not necessary to use the whole budget.

I made a list of $q$ pairs of integers $(a_{j},b_{j})$ , which means I may visit the store at time $a_{j}$ , and spend at most $b_{j}$ dollars at the store. For each pair, I'd like to know the maximum happiness I can obtain. But there are so many pairs that I can't handle them. Can you help me?

The first line contains two space-separated integers $n$ and $p$ ( $1<=n<=4000$ , $1<=p<=10000$ ) — the number of items, and the display time of each item.

Next $n$ lines describe the items. The $i$ -th ( $1<=i<=n$ ) of them contains three space-separated integers $c_{i}$ , $h_{i}$ , $t_{i}$ ( $1<=c_{i},h_{i}<=4000$ , $1<=t_{i}<=10000$ ) — the cost of the $i$ -th item, the happiness of the $i$ -th item, and the time when the $i$ -th item starts to be displayed.

The next line contains an integer $q$ ( $1<=q<=20000$ )— the number of candidates.

Next $q$ lines describe the candidates. The $j$ -th ( $1<=j<=q$ ) of them contains two space-separated integers $a_{j}$ , $b_{j}$ ( $1<=a_{j}<=20000$ , $1<=b_{j}<=4000$ ) — the visit time and the budget for $j$ -th visit of store.

For each candidate, print a single line containing the maximum happiness that I can obtain by buying some items.