都说是$CTSC2018$最水的题。。。还是太蒻了想了很长时间。。。$QAQ$
考虑一下朴素的解法：
对$d_i$排序，对$d_i$二分答案。因为答案取的是最小值，所以比它大的随便加。$d_i$越小能加的范围就越大，答案具有单调性，因此可以二分。然后尽可能把所有较小的$p_i$加上，看看加到最大后$\sum l_i$是否满足，以此判断二分范围。
复杂度$O(n^2logn)$
瓶颈在于选取尽可能多得选取较小的$p_i$。可以发现它能用主席树维护。首先按$p_i$排序，获取每种果汁$p_i$的排名；再按$d_i$排序，依次按照$p_i$的排名插入主席树，每个节点维护一下$\sum p_i*l_i$（把这些果汁全加上的价格）和$\sum l_i$（这些果汁的总容量）。
查询时，尽可能把左儿子选上，也就是只要$\sum p_i*l_i \le g_j$就把总容量加上$\sum l_i$，$g_j$减去$\sum p_i*l_i$，走右儿子。当然可能出现递归到叶子节点，剩余的$g_j$不足以全加上这种果汁，尽可能多加，即返回$min\{g_j/p_i,l_i\}$。
总之都是基于贪心思想。其他过程还是和开始的做法一样。时间复杂度$O(nlog^2n)$
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<typename T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int root[maxn];
struct Drink{
int d,l,num;
long long p;
}d[maxn];
struct Chairman_Tree{
int ls[maxn<<5],rs[maxn<<5],cnt;
long long sum[maxn<<5],con[maxn<<5],p[maxn<<5];
//sum是li*pi的和，con是li的和，p是叶子节点的pi
#define ls(x) ls[x]
#define rs(x) rs[x]
void build(int poi,int l,int r,int &node,int ol,long long L,long long P){
node=++cnt;
sum[node]=sum[ol]+L*P;
con[node]=con[ol]+L;
if(l==r){
p[node]=P;
return;
}
int mid=l+r>>1;
if(poi<=mid)rs(node)=rs(ol),build(poi,l,mid,ls(node),ls(ol),L,P);
else ls(node)=ls(ol),build(poi,mid+1,r,rs(node),rs(ol),L,P);
}
long long ask(int l,int r,int node,long long g){
if(l==r)return node?min((g/p[node]),con[node]):0;
//空节点注意判断一下，否则会出现除以0的情况
int mid=l+r>>1;
if(sum[ls(node)]>g)return ask(l,mid,ls(node),g);
//剩下的钱不足以全加上，走左儿子
else return ask(mid+1,r,rs(node),g-sum[ls(node)])+con[ls(node)];
//付得起，贪心全加上，走右儿子
}
}ct;
inline bool cmp1(Drink x,Drink y){
return x.p<y.p;
}
inline bool cmp2(Drink x,Drink y){
return x.d>y.d;
}
int main(){
int n=read(),m=read();
for(register int i=1;i<=n;++i)
d[i].d=read(),d[i].p=read<long long>(),d[i].l=read();
sort(d+1,d+1+n,cmp1);//按pi排序
for(register int i=1;i<=n;++i)
d[i].num=i;//获取排名
sort(d+1,d+1+n,cmp2);//按di排序
for(register int i=1;i<=n;++i)
ct.build(d[i].num,1,n,root[i],root[i-1],d[i].l,d[i].p);
//以pi的排名建树
int l,r;
while(m--){
long long g=read<long long>(),L=read<long long>();
int ans=-1;
l=1,r=n;
while(l<=r){
int mid=l+r>>1;
long long k=ct.ask(1,n,root[mid],g);
if(k>=L)ans=d[mid].d,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
}
}
