New Year Shopping

有 $n$ 种商品，第 $i$ 种商品的价格是 $c_i$ ，购买后可以增加 $h_i$ 的快乐指数，将于第 $t_i$ 天上市。商品的保质期为 $p$ 天，过期后不能再购买，即第 $i$ 种商品只能在第 $t_i$ 天到第 $t_i+p-1$ 天之间购买，每种商品只能购买一次。 有 $q$ 个询问，每次给定两个整数 $a,b$ ，求在第 $a$ 天去购物，最多使用 $b$ 元的情况下可以得到的最大快乐指数。询问之间互不干扰。 输入格式 第一行有两个整数：$n,p$ 。 接下来 $n$ 行，每行有三个整数，分别表示 $c_i,h_i,t_i$ 。 接下来有一个整数 $q$ 。 最后 $q$ 行，每行两个整数 $a,b$ 代表一次询问。 输出格式 共输出 $q$ 行，每行表示对应询问的答案。 数据范围 $1\le n\le 4\times 10^3, 1\le p \le 10^4$ $1\le c_i,h_i \le 4\times 10^3, 1\le t_i \le 10^4$ $1\le q \le 2\times 10^4,1\le a \le 2\times 10^4, 1\le b \le 4\times 10^3$

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.

4 4
2 3 2
3 5 1
4 7 2
11 15 5
4
1 3
2 5
2 6
5 14

5
8
10
18

5 4
3 2 1
7 4 4
2 1 2
6 3 5
3 2 2
10
1 5
2 5
4 8
4 9
4 10
5 8
5 9
5 10
8 4
7 9

2
3
5
5
6
4
5
6
0
4

Consider the first sample. 1. At time 1, only the 2nd item is available. I can buy the 2nd item using 3 dollars and my happiness will increase by 5. 2. At time 2, the 1st, 2nd, and 3rd item is available. I can buy the 1st item using 2 dollars, and the 2nd item using 3 dollars. My happiness will increase by 3 + 5 = 8. 3. At time 2, the 1st, 2nd, and 3rd item is available. I can buy the 1st item using 2 dollars, and the 3nd item using 4 dollars. My happiness will increase by 3 + 7 = 10. 4. At time 5, the 1st, 3rd, and 4th item is available. I can buy the 1st item using 2 dollars, and the 4th item using 11 dollars. My happiness will increase by 3 + 15 = 18. Note that I don't need to use the whole budget in this case.