40pts 玄关求条/HACK

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,Inf=2e9;
int t,n,q;
int gs[N];
int a,b,lst,cnt,lm;
long long m;
struct seq {
    int id;
    long long mn,sm;
} mx[N];
int main() {
	cin>>t;
	while(t--) {
		cin>>n>>q;
		lst=-1,gs[0]=Inf,lm=n;
		for(int i=1;i<=n;i++) {
			cin>>a>>b;
			if(a!=lst+1) gs[i]=0,lm=i-1;
			else gs[i]=min(gs[i-1],b);
			lst=a;
		}
		int pos=n;
        cnt=0;
		while(pos!=0) {
            while(gs[pos]==gs[pos+1]) pos--;
            if(pos==0) break;
			mx[++cnt].id=pos;
            mx[cnt].mn=gs[pos+1];
            mx[cnt].sm=mx[cnt-1].sm+1ll*pos*(gs[pos]-gs[pos+1]);
            pos--;
        }
		for(int i=1;i<=q;i++) {
			cin>>m;
			if(m==0) {
				if(gs[1]!=0) cout<<-1<<endl;
				else cout<<1<<endl;
				continue;
			}
			if(m<lm) {
				cout<<2<<endl;
				continue;
			}
			int l=1,r=cnt,mid,res=-1;
			while(l<=r) {
				mid=(l+r)/2;
				if(mx[mid].sm>=m) res=mid,r=mid-1;
				else l=mid+1;
			}
            if(res==-1) {
                cout<<-1<<endl;
                continue;
            }
			mid=res;
			m-=mx[mid-1].sm;
			res=mx[mid].mn+m/mx[mid].id;
			if(m%mx[mid].id) res++;
			cout<<res<<endl;
		}
	}
}