U615418 market

题目描述

三阳路一共有 $n$ 家商店，每家商店只卖一种物品，其中第 $i$ 家商店的物品单价为 $a_i$ ，价值为 $b_i$ ，该商店在 $t_i$ 时刻才开始营业。

小a 计划在一天的 m 个时间外出购物，第 i 次外出的时间是 $T_i$ ，携带的金额为 $M_i$ ，每次外出他可以在每一家正在营业的商店购买至多一件物品。

小a 想知道他每一次外出时最多可以购买多少总价值的物品。

小a很慷慨，每次外出多余的钱会分给同学，不会留给下一次外出。

第一行包含两个正整数 $n, m$ ，表示商店的总数和小a外出的次数。

接下来 $n$ 行，每行三个正整数 $a_i, b_i, t_i$

接下来 $m$ 行，每行两个正整数 $T_i, M_i$

输出 $m$ 行，每行一个整数，表示该次外出小a能买到的最大总价值。

10
12

测试点编号	$n$	$m$	$a_i, M_i$	$b_i$	$t_i, T_i$
1	$= 10$	$= 5$	$\le 10$
2	$= 20$	$= 10$	$\le 100$		$\le 20$
3	$= 100$	$= 1$	$\le 100$		$= 1$
4	$= 200$	$= 1$	$\le 200$		$= 1$
5	$= 150$	$= 100000$	$\le 150$
6	$= 300$		$\le 300$	$\le 300$	$\le 300$
7	$= 20$		$\le 10^9$	$\le 300$	$\le 20$
8	$= 200$			$\le 200$
9	$= 300$			$\le 300$
10	$= 300$			$\le 300$