Home => ProblemSet => 3.16-03:[CTSC2018] 混合果汁
2026: 3.16-03:[CTSC2018] 混合果汁
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 0 Solved: 0[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
小 R 热衷于做黑暗料理，尤其是混合果汁。
商店里有 n 种果汁，编号为 0,1,⋯,n−1 。i 号果汁的美味度是 di，每升价格为 pi。小 R 在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，i 号果汁最多只能添加 li 升。
现在有 m 个小朋友过来找小 R 要混合果汁喝，他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中，第 j 个小朋友希望他得到的混合果汁总价格不大于 gj，体积不小于 Lj。在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。
商店里有 n 种果汁，编号为 0,1,⋯,n−1 。i 号果汁的美味度是 di，每升价格为 pi。小 R 在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，i 号果汁最多只能添加 li 升。
现在有 m 个小朋友过来找小 R 要混合果汁喝，他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中，第 j 个小朋友希望他得到的混合果汁总价格不大于 gj，体积不小于 Lj。在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。
Input
输入第一行包含两个正整数 n,m，表示果汁的种数和小朋友的数量。
接下来 n 行，每行三个正整数 di,pi,li，表示 i 号果汁的美味度为 di，每升价格为 pi，在一瓶果汁中的添加上限为 li。
接下来 m 行依次描述所有小朋友：每行两个数正整数 gj,Lj 描述一个小朋友，表示他最多能支付 gj 元钱，他想要至少 Lj 升果汁。
接下来 n 行，每行三个正整数 di,pi,li，表示 i 号果汁的美味度为 di，每升价格为 pi，在一瓶果汁中的添加上限为 li。
接下来 m 行依次描述所有小朋友：每行两个数正整数 gj,Lj 描述一个小朋友，表示他最多能支付 gj 元钱，他想要至少 Lj 升果汁。
Output
对于所有小朋友依次输出：对于每个小朋友，输出一行，包含一个整数，表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求，则输出 −1。
Sample Input Copy
3 4
1 3 5
2 1 3
3 2 5
6 3
5 3
10 10
20 10
Sample Output Copy
3
2
-1
1
HINT
