CF500F.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?

都贤正在经营一家杂货店。他出售编号为 $1$ 到 $n$ 的 $n$ 种商品。第 $i$ 种商品（$1 \le i \le n$）售价为 $c_i$ 美元，购买后可使我的幸福感增加 $h_i$。由于新鲜度限制，每种商品仅能展示 $p$ 个时间单位。若都贤在时刻 $t_i$ 开始展示第 $i$ 种商品，则顾客仅能在区间 $[t_i,\, t_i + (p - 1)]$（含端点）内购买该商品。此外，每位顾客不能重复购买同一种商品。

我打算前往都贤的杂货店为新年派对采购一些商品，并使总幸福感最大化。但由于我非常忙碌，只能访问该店一次，且停留时间极短。换言之，若我在时刻 $t$ 访问该店，则我仅能购买在时刻 $t$ 正在展示的商品。只要预算允许，我可以购买任意数量的商品（但受库存和规则限制）；根据店铺规定，同一种商品不可重复购买。不必花光全部预算。

我已列出 $q$ 对整数 $(a_j,\, b_j)$，表示我可能于时刻 $a_j$ 访问该店，且在店内最多花费 $b_j$ 美元。对每一对 $(a_j,\, b_j)$，我想知道此时所能获得的最大幸福感。但这样的数对太多，我无法逐一处理。你能帮我解决吗？

The first line contains two space-separated integers n and p (1 ≤ n ≤ 4000, 1 ≤ p ≤ 10 000) — 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 ≤ 10 000) — 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 ≤ 20 000)— 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 ≤ 20 000, 1 ≤ b__j ≤ 4000) — the visit time and the budget for j-th visit of store.

第一行包含两个以空格分隔的整数 $n$ 和 $p$（$1 \leq n \leq 4000$，$1 \leq p \leq 10\,000$）—— 分别表示物品数量以及每个物品的展示时长。

接下来 $n$ 行描述这些物品。其中第 $i$ 行（$1 \leq i \leq n$）包含三个以空格分隔的整数 $c_i$、$h_i$、$t_i$（$1 \leq c_i, h_i \leq 4000$，$1 \leq t_i \leq 10\,000$）—— 分别表示第 $i$ 个物品的成本、带来的幸福感，以及该物品开始展示的时间。

下一行包含一个整数 $q$（$1 \leq q \leq 20\,000$）—— 表示候选顾客的数量。

接下来 $q$ 行描述这些候选顾客。其中第 $j$ 行（$1 \leq j \leq q$）包含两个以空格分隔的整数 $a_j$、$b_j$（$1 \leq a_j \leq 20\,000$，$1 \leq b_j \leq 4000$）—— 分别表示第 $j$ 位顾客的到店时间与预算。

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

对于每位候选人，输出一行，包含我通过购买某些物品所能获得的最大幸福感。

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.

考虑第一个样例。

1. 在时刻 1，仅有第 2 个物品可用。我可以用 3 美元购买第 2 个物品，幸福感增加 5。
2. 在时刻 2，第 1、第 2 和第 3 个物品均可用。我可以用 2 美元购买第 1 个物品，用 3 美元购买第 2 个物品，幸福感增加 $3 + 5 = 8$。
3. 在时刻 2，第 1、第 2 和第 3 个物品均可用。我可以用 2 美元购买第 1 个物品，用 4 美元购买第 3 个物品，幸福感增加 $3 + 7 = 10$。
4. 在时刻 5，第 1、第 3 和第 4 个物品可用。我可以用 2 美元购买第 1 个物品，用 11 美元购买第 4 个物品，幸福感增加 $3 + 15 = 18$。注意：在此情况下，我不必花光全部预算。