题目描述

有 $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$ 行，每行表示对应询问的答案。

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

提示

$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$。