#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int nitem, tshow;
int cost[4000], val[4000], st[4000];
int nq;
int qt[20000], qhave[20000], qret[20000];
int fst[30001], nxt[4000];
int qfst[20001][2], qnxt[20000];
int pval[5001][4001];
int sval[5001][4001];
void run() {
  scanf("%d%d", &nitem, &tshow);
  for (int i = (0); i < (nitem); ++i)
    scanf("%d%d%d", &cost[i], &val[i], &st[i]);
  scanf("%d", &nq);
  for (int i = (0); i < (nq); ++i) scanf("%d%d", &qt[i], &qhave[i]);
  int bsize = min(5000, tshow);
  memset(fst, -1, sizeof(fst));
  for (int i = (0); i < (nitem); ++i) {
    nxt[i] = fst[st[i]];
    fst[st[i]] = i;
  }
  memset(qfst, -1, sizeof(qfst));
  for (int i = (0); i < (nq); ++i) {
    int blck = qt[i] / bsize,
        nfull = (blck * bsize + tshow - qt[i] - 1) / bsize;
    qnxt[i] = qfst[blck][nfull];
    qfst[blck][nfull] = i;
  }
  for (int i = (0); i < (nq); ++i) qret[i] = -1;
  for (int blck = 0; blck * bsize <= 20000; ++blck)
    for (int nfull = (0); nfull < (2); ++nfull)
      if (qfst[blck][nfull] != -1) {
        for (int j = (0); j <= (4000); ++j) pval[0][j] = sval[0][j] = 0;
        if (blck > 0 && nfull > 0)
          for (int i = (0); i < (bsize); ++i)
            for (int x = fst[blck * bsize - i - 1]; x != -1; x = nxt[x])
              for (int j = 4000 - cost[x]; j >= 0; --j)
                if (sval[0][j] + val[x] > sval[0][j + cost[x]])
                  sval[0][j + cost[x]] = sval[0][j] + val[x];
        for (int i = (0); i < (bsize); ++i) {
          for (int j = (0); j <= (4000); ++j)
            pval[i + 1][j] = pval[i][j], sval[i + 1][j] = sval[i][j];
          for (int x = fst[blck * bsize + i]; x != -1; x = nxt[x]) {
            for (int j = 4000 - cost[x]; j >= 0; --j)
              if (pval[i + 1][j] + val[x] > pval[i + 1][j + cost[x]])
                pval[i + 1][j + cost[x]] = pval[i + 1][j] + val[x];
          }
          if (blck - nfull > 0)
            for (int x = fst[(blck - nfull) * bsize - i - 1]; x != -1;
                 x = nxt[x]) {
              for (int j = 4000 - cost[x]; j >= 0; --j)
                if (sval[i + 1][j] + val[x] > sval[i + 1][j + cost[x]])
                  sval[i + 1][j + cost[x]] = sval[i + 1][j] + val[x];
            }
        }
        for (int qi = qfst[blck][nfull]; qi != -1; qi = qnxt[qi]) {
          int pcnt = qt[qi] - blck * bsize + 1,
              scnt = tshow - pcnt - nfull * bsize;
          qret[qi] = 0;
          for (int phave = (0); phave <= (qhave[qi]); ++phave) {
            int shave = qhave[qi] - phave;
            int cur = sval[scnt][shave] + pval[pcnt][phave];
            if (cur > qret[qi]) qret[qi] = cur;
          }
        }
      }
  for (int qi = (0); qi < (nq); ++qi) printf("%d\n", qret[qi]);
}
int main() {
  run();
  return 0;
}
