P4602 [CTSC2018] 混合果汁

小 R 热衷于做黑暗料理，尤其是混合果汁。 商店里有 $n$ 种果汁，编号为 $0,1,\cdots,n-1$ 。$i$ 号果汁的美味度是 $d_i$，每升价格为 $p_i$。小 R 在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，$i$ 号果汁最多只能添加 $l_i$ 升。 现在有 $m$ 个小朋友过来找小 R 要混合果汁喝，他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中，第 $j$ 个小朋友希望他得到的混合果汁总价格不大于 $g_j$，体积不小于 $L_j$。在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

无

无

对于所有的测试数据，保证 $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$|无