#2555. 「CTSC2018」混合果汁

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 R 热衷于做黑暗料理,尤其是混合果汁。

商店里有 nn 种果汁,编号为 0,1,2,...,n10, 1, 2, . . . , n − 1ii 号果汁的美味度是 did_i,每升价格为 pip_i。小 R 在制作混合果汁时,还有一些特殊的规定,即在一瓶混合果汁中,ii 号果汁最多只能添加 lil_i 升。

现在有 mm 个小朋友过来找小 R 要混合果汁喝,他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中,第 jj 个小朋友希望他得到的混合果汁总价格不大于 gjg_j,体积不小于 LjL_j。在上述这些限制条件下,小朋友们还希望混合果汁的美味度尽可能地高,一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

输入格式

输入第一行包含两个正整数 n,mn, m,表示果汁的种数和小朋友的数量。接下来 nn 行,每行三个正整数 di,pi,lid_i, p_i, l_i,表示 ii 号果汁的美味度为 did_i,每升价格为pip_i,在一瓶果汁中的添加上限为 lil_i

接下来 mm 行依次描述所有小朋友:每行两个数正整数 gj,Ljg_j, L_j 描述一个小朋友,表示他最多能支付 gjg_j 元钱,他想要至少 LjL_j 升果汁。

输出格式

对于所有小朋友依次输出:对于每个小朋友,输出一行,包含一个整数,表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求,则输出 1−1

样例

样例输入 1

3 4
1 3 5
2 1 3
3 2 5
6 3
5 3
10 10
20 10

样例输出 1

3
2
-1
1

样例 2

见附加文件中的 juice2.injuice2.ans

样例 3

见附加文件中的 juice3.injuice3.ans

数据范围与提示

对于所有的测试数据,保证 n,m100000n, m \le 1000001di,pi,li1051gj,Lj10181 \le d_i, p_i, l_i \le 10^5,1 \le g_j, L_j \le 10^{18}

测试点编号n=n=m=m=其他限制
1,2,31,2,310101010
4,5,64,5,6500500500500
7,8,97,8,95000500050005000
10,11,1210,11,12100000100000100000100000pi=1p_i=1
13,14,1513,14,15100000100000100000100000li=1l_i=1
16,17,18,19,2016,17,18,19,20100000100000100000100000