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?

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.

Examples

input

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

output

5
8
10
18

input

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

output

2
3
5
5
6
4
5
6
0
4

Note

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.

Solution:

#include <cstring>
#include <vector>
#include  <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

using namespace std;

const int MAX = 4010;

int c[MAX], h[MAX], t[MAX];
pair <int, int> e[MAX];
int nc[MAX], nh[MAX], nt[MAX];
int f[MAX];
int l_to_r[MAX][MAX];
int r_to_l[MAX][MAX];

int main() {
int n, p;
scanf("%d %d", &n, &p);
for (int i = 0; i < n; i++) {
    scanf("%d %d %d", c + i, h + i, t + i);
    e[i] = make_pair(t[i], i);
  }
  sort(e, e + n);
  for (int i = 0; i < n; i++) {
    int id = e[i].second;
    nc[i] = c[id];
    nh[i] = h[id];
    nt[i] = t[id];
  }
  for (int i = 0; i < n; i++) {
    c[i] = nc[i];
    h[i] = nh[i];
    t[i] = nt[i];
  }
  int beg = 0;
  while (beg < n) {
    int end = beg;
    while (end + 1 < n && t[end + 1] / p == t[beg] / p) {
      end++;
    }
    {
      for (int j = 0; j < MAX; j++) {
        f[j] = 0;
      }
      for (int id = beg; id <= end; id++) {
        for (int j = MAX - 1 - c[id]; j >= 0; j--) {
if (f[j] + h[id] > f[j + c[id]]) {
f[j + c[id]] = f[j] + h[id];
}
}
for (int j = 0; j < MAX; j++) {
          l_to_r[id][j] = f[j];
        }
      }
    }
    {
      for (int j = 0; j < MAX; j++) {
        f[j] = 0;
      }
      for (int id = end; id >= beg; id--) {
for (int j = MAX - 1 - c[id]; j >= 0; j--) {
if (f[j] + h[id] > f[j + c[id]]) {
f[j + c[id]] = f[j] + h[id];
}
}
for (int j = 0; j < MAX; j++) {
          r_to_l[id][j] = f[j];
        }
      }
    }
    beg = end + 1;
  }
  int tt;
  scanf("%d", &tt);
  while (tt--) {
    int foo, bar;
    scanf("%d %d", &foo, &bar);
    int first = -1, last = -1;
    for (int i = 0; i < n; i++) {
      if (t[i] <= foo && foo <= t[i] + p - 1) {
        if (first == -1) {
          first = i;
        }
        last = i;
      }
    }
    if (first == -1) {
      printf("%d\n", 0);
      continue;
    }
    if (t[first] / p == foo / p) {
      printf("%d\n", l_to_r[last][bar]);
      continue;
    }
    if (t[last] / p == foo / p - 1) {
      printf("%d\n", r_to_l[first][bar]);
      continue;
    }
    int ans = 0;
    for (int part = 0; part <= bar; part++) {
      int cur = l_to_r[last][part] + r_to_l[first][bar - part];
      if (cur > ans) {
ans = cur;
}
}
printf("%d\n", ans);
}
return 0;
}