题目描述

  在比特镇一共有 $n$ 家商店，编号依次为 $1$ 到 $n$。每家商店只会卖一种物品，其中第 $i$ 家商店的物品单价为 $c_i$，价值为 $v_i$，且该商店开张的时间为 $t_i$。

  $Byteasar$ 计划进行 $m$ 次购物，其中第 $i$ 次购物的时间为 $T_i$，预算为 $M_i$。每次购物的时候，$Byteasar$ 会在每家商店购买最多一件物品，当然他也可以选择什么都不买。如果购物的时间早于商店开张的时间，那么显然他无法在这家商店进行购物。

  现在 $Byteasar$ 想知道，对于每个计划，他最多能购入总价值多少的物品。请写一个程序，帮助 $Byteasar$ 合理安排购物计划。

  注意：每次所花金额不得超过预算，预算也不一定要花完，同时预算不能留给其它计划使用。

输入格式

  第一行包含两个正整数 $n,m$，表示商店的总数和计划购物的次数。

  接下来 $n$ 行，每行三个正整数 $c_i,v_i,t_i$，分别表示每家商店的单价、价值以及开张时间。

  接下来 $m$ 行，每行两个正整数 $T_i,M_i$，分别表示每个购物计划的时间和预算。

输出格式

  输出 $m$ 行，每行一个整数，对于每个计划输出最大可能的价值和。

输入样例

5 2
5 5 4
1 3 1
3 4 3
6 2 2
4 3 2
3 8
5 9

10
12

样例解释

  第一个计划可以在商店 $2,3,5$ 各购买一件物品，总花费为 $1+3+4=8$，总价值为 $3+4+3=10$。

  第二个计划可以在商店 $1,2,3$ 各购买一件物品，总花费为 $5+1+3=9$，总价值为 $5+3+4=12$。

数据范围与约定

  对于 $100\%$ 的数据，$1\leqslant t_i,T_i\leqslant n$。