二分答案，查询最小花费即可。用主席树来维护就好啦
#include <bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f #define N 100010 inline char gc(){ static char buf[1<<16],*S,*T; if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;} return *S++; } inline ll read(){ ll x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f; } int n,m,rt[N],owo=0,nn,b[N]; struct data{ int d,p,l; friend bool operator<(data a,data b){return a.d>b.d;} }a[N]; struct node{ int lc,rc;ll sum,x; }tr[N*20]; inline void ins(int &p,int l,int r,int x,int y){ tr[++owo]=tr[p];p=owo;tr[p].x+=y;tr[p].sum+=(ll)x*y; if(l==r) return;int mid=l+r>>1; if(x<=mid) ins(tr[p].lc,l,mid,x,y); else ins(tr[p].rc,mid+1,r,x,y); } inline ll ask(int p,int l,int r,ll x){ if(l==r) return x*l; int mid=l+r>>1; if(x<=tr[tr[p].lc].x) return ask(tr[p].lc,l,mid,x); return tr[tr[p].lc].sum+ask(tr[p].rc,mid+1,r,x-tr[tr[p].lc].x); } inline bool jud(int mid,ll x,ll K){ if(tr[rt[mid]].x<x) return 0; return ask(rt[mid],1,1e5,x)<=K; } int main(){ // freopen("juice.in","r",stdin); // freopen("juice.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;++i) a[i].d=read(),a[i].p=read(),a[i].l=read(); sort(a+1,a+n+1); for(int i=1,j;i<=n;i=j){ rt[nn+1]=rt[nn];++nn;j=i;b[nn]=a[i].d; while(a[j].d==a[i].d&&j<=n) ins(rt[nn],1,1e5,a[j].p,a[j].l),++j; }while(m--){ ll K=read(),x=read(); int l=1,r=nn; while(l<=r){ int mid=l+r>>1; if(jud(mid,x,K)) r=mid-1; else l=mid+1; }if(r+1>nn) puts("-1"); else printf("%d\n",b[r+1]); }return 0; }