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?

Input

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.

Output

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

Note

Consider the first sample.

$\text{[math]}$

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

New Year Shopping

Examples