考慮對于單次詢問，顯然可以二分，每次將美味度大于等于 \(mid\) 的果汁放在一起按價格排序，貪心地計算能否在 \(g_j\) 的限制內買夠 \(L_j\) 的果汁。

多次詢問可二分的問題，這提醒我們去做整體二分。但是有一個問題，我們無法在整體二分搜索樹上的每個節點都對大于等于 \(mid\) 的果汁進行排序計算，不然顯然會炸。有一個解決方案是，將一堆沒有交集的搜索樹節點放在一起計算，用線段樹維護按美味度排序后的某個后綴果汁集合。具體地，按照美味度倒著掃，對于每個美味度在 \([L,R]\) 的搜索樹節點，我們先將 \([mid+1,R]\) 的果汁加入線段樹，然后處理節點上的詢問，再將 \([L,mid]\) 的果汁加入線段樹。換言之，我們要按層遍歷搜索樹，并且每一層還要倒著遍歷！一個方案是用 std::vector 存儲當前層的搜索樹節點寫 bfs。時間復雜度 \(O((n+m)\log^2n)\)。

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,lsh[maxn];
ll ans[maxn];
struct jui{
	int d,p,l;
}a[maxn];
struct{
	int id;
	ll g,l;
}b[maxn],hp[maxn];
int rt,tot;
struct{
	int ls,rs,d,p,l;
	ll smp,sml;
}tr[maxn<<1];
#define ls(id) tr[id].ls
#define rs(id) tr[id].rs
#define d(id) tr[id].d
#define p(id) tr[id].p
#define l(id) tr[id].l
#define smp(id) tr[id].smp
#define sml(id) tr[id].sml
il void pushup(int id){
	smp(id)=smp(ls(id))+smp(rs(id));
	sml(id)=sml(ls(id))+sml(rs(id));
}
il void insert(int &id,int L,int R,int p,int d,int l){
	if(!id){
		id=++tot;
		ls(id)=rs(id)=0;
		d(id)=p(id)=l(id)=0;
		smp(id)=sml(id)=0;
	}
	if(L==R){
		smp(id)=lsh[p]*1ll*l;
		sml(id)=l;
		d(id)=d,p(id)=lsh[p],l(id)=l;
		return ;
	}
	int mid=(L+R)>>1;
	if(p<=mid){
		insert(ls(id),L,mid,p,d,l);
	}
	else{
		insert(rs(id),mid+1,R,p,d,l);
	}
	pushup(id);
}
il ll query(int id,int L,int R,ll g){
	if(!id){
		return 0;
	}
	if(L==R){
		return min(g/p(id),l(id)*1ll);
	}
	int mid=(L+R)>>1;
	if(smp(ls(id))>=g){
		return query(ls(id),L,mid,g);
	}
	else{
		return query(rs(id),mid+1,R,g-smp(ls(id)))+sml(ls(id));
	}
}
#undef ls
#undef rs
#undef d
#undef p
#undef l
#undef smp
#undef sml
struct node{
	int L,R,l,r;
	node(int L=0,int R=0,int l=0,int r=0):L(L),R(R),l(l),r(r){}
};
vector<node> q[2];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].d>>a[i].p>>a[i].l;
	}
	sort(a+1,a+n+1,[](const jui &x,const jui &y){return x.p<y.p;});
	for(int i=1;i<=n;i++){
		lsh[i]=a[i].p;
		a[i].p=i;
	}
	sort(a+1,a+n+1,[](const jui &x,const jui &y){return x.d>y.d;});
	for(int i=1;i<=m;i++){
		cin>>b[i].g>>b[i].l;
		b[i].id=i;
	}
	q[0].pb(node(1,1e5,1,m));
	int cur=0;
	while(q[cur].size()){
		q[cur^1].clear();
		int now=1;
		rt=tot=0;
		for(node x:q[cur]){
			int L=x.L,R=x.R,l=x.l,r=x.r;
//			cout<<L<<" "<<R<<":\n";
//			for(int i=l;i<=r;i++){
//				cout<<b[i].id<<" ";
//			}
//			puts("");
			if(l>r){
				continue;
			}
			if(L==R){
				while(now<=n&&a[now].d>=L){
					insert(rt,1,n,a[now].p,a[now].d,a[now].l);
					now++;
				}
				for(int i=l;i<=r;i++){
					if(query(rt,1,n,b[i].g)>=b[i].l){
						ans[b[i].id]=L;
					}
					else{
						ans[b[i].id]=-1;
					}
				}
				continue;
			}
			int mid=(L+R)>>1;
			while(now<=n&&a[now].d>mid){
				insert(rt,1,n,a[now].p,a[now].d,a[now].l);
				now++;
			}
			int pl=l,pr=r;
			for(int i=l;i<=r;i++){
				if(query(rt,1,n,b[i].g)>=b[i].l){
					hp[pr--]=b[i];
				}
				else{
					hp[pl++]=b[i];
				}
			}
			for(int i=l;i<pl;i++){
				b[i]=hp[i];
			}
			for(int i=pl;i<=r;i++){
				b[i]=hp[i]; 
			}
			q[cur^1].pb(node(mid+1,R,pl,r));
			q[cur^1].pb(node(L,mid,l,pr));
			while(now<=n&&a[now].d>=L){
				insert(rt,1,n,a[now].p,a[now].d,a[now].l);
				now++;
			}
		}
		cur^=1;
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}
}
int main(){return asbt::main();}