4558: 「CTSC2018」混合果汁
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
小 R 热衷于做黑暗料理，尤其是混合果汁。
商店里有 $n$ 种果汁，编号为 $0, 1, 2, . . . , n − 1$。$i$ 号果汁的美味度是 $d_i$，每升价格为 $p_i$。小 R 在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，$i$ 号果汁最多只能添加 $l_i$ 升。
现在有 $m$ 个小朋友过来找小 R 要混合果汁喝，他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中，第 $j$ 个小朋友希望他得到的混合果汁总价格不大于 $g_j$，体积不小于 $L_j$。在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。
输入
输入第一行包含两个正整数 $n, m$，表示果汁的种数和小朋友的数量。接下来 $n$ 行，每行三个正整数 $d_i, p_i, l_i$，表示 $i$ 号果汁的美味度为 $d_i$，每升价格为$p_i$，在一瓶果汁中的添加上限为 $l_i$。
接下来 $m$ 行依次描述所有小朋友：每行两个数正整数 $g_j, L_j$ 描述一个小朋友，表示他最多能支付 $g_j$ 元钱，他想要至少 $L_j$ 升果汁。
输出
对于所有小朋友依次输出：对于每个小朋友，输出一行，包含一个整数，表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求，则输出 $−1$。
样例输入 复制
3 4
1 3 5
2 1 3
3 2 5
6 3
5 3
10 10
20 10样例输出 复制
3
2
-1
1提示
数据范围：对于所有的测试数据，保证 $n, m \le 100000$，$1 \le d_i, p_i, l_i \le 10^5，1 \le g_j, L_j \le 10^{18}$。 | 测试点编号 | $n=$ | $m=$ | 其他限制 | | :-: | :-: | :-: | :-: | | $1,2,3$| $10$ | $10$ | 无 | | $4,5,6$ | $500$ | $500$ | 无 | | $7,8,9$ | $5000$ | $5000$ | 无 | | $10,11,12$ | $100000$ | $100000$ | $p_i=1$ | | $13,14,15$ | $100000$ | $100000$ | $l_i=1$ | | $16,17,18,19,20$ | $100000$ | $100000$ | 无 |