Dohyun 正在经营一家杂货店。他出售 n 件物品,编号为 1 到 n 的整数。其中第 i 个(1 ≤ i ≤ n)花费 ci 美元,如果我买了它,我的幸福感就会增加 hi。由于新鲜度,每个项目只能显示 p 个时间单位。由于 Dohyun 在时间 ti 展示第 i 件商品,因此顾客只能在时间 ti 到时间 ti + (p - 1) 期间购买第 i 件商品。此外,每个顾客不能多次购买同一商品。
我想去道贤的杂货店买一些新年聚会的物品,最大化我的幸福。因为我是一个非常忙碌的人,所以我只能去一次商店,而且时间很短。换句话说,如果我在时间 t 访问商店,我只能购买时间 t 可用的商品。但如果预算允许的话,我可以购买尽可能多的物品。由于商店规定,我不能多次购买同一商品。没有必要使用全部预算。
我列出了 q 对整数 (aj, bj) 的列表,这意味着我可能会在 aj 时间访问商店,并在商店最多花费 bj 美元。对于每一对,我想知道我可以获得的最大幸福。但数量太多,我应付不了。你能帮助我吗?
输入
第一行包含两个空格分隔的整数 n 和 p (1 ≤ n ≤ 4000, 1 ≤ p ≤ 10 000) — 项目数以及每个项目的显示时间。
接下来的 n 行描述了这些项目。其中第 i 个 (1 ≤ i ≤ n) 包含三个空格分隔的整数 ci, hi, ti (1 ≤ ci, hi ≤ 4000, 1 ≤ ti ≤ 10 000) — 第 i 个项目的成本、第 i 个项目的幸福度以及第 i 个项目开始显示的时间。
下一行包含一个整数 q (1 ≤ q ≤ 20 000)——候选者的数量。
接下来 q 行描述候选者。其中第 j 个 (1 ≤ j ≤ q) 包含两个空格分隔的整数 aj, bj (1 ≤ aj ≤ 20 000, 1 ≤ bj ≤ 4000) — 第 j 次访问商店的访问时间和预算。
输出
对于每个候选人,打印一行包含我可以通过购买一些物品获得的最大幸福感。
示例
输入 #1
4 4 2 3 2 3 5 1 4 7 2 11 15 5 4 1 3 2 5 2 6 5 14
输出 #1
5 8 10 18
输入 #2
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
2 3 5 5 6 4 5 6 0 4
注意
考虑第一个样本。
1. 在时间 1,只有第 2 项可用。我可以用 3 美元购买第二件物品,我的幸福感会增加 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。请注意,在这种情况下我不需要使用全部预算。