Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define INF 1LL<<60
typedef long long ll;
typedef pair<ll,int> P;
vector<ll> dif;
vector<P> dif2;

class segtree{
public:
	static const int N=1<<17;
	ll dp[1<<18];
	int cnt[1<<18];
	segtree(){
		memset(dp,0,sizeof(dp));
		memset(cnt,0,sizeof(cnt));
	}

	void update(int k,P p){
		k+=N-1;
		cnt[k]+=p.first;
		dp[k]+=p.second;
		while(k>0){
			k=(k-1)/2;
			dp[k]=dp[k*2+1]+dp[k*2+2];
			cnt[k]=cnt[k*2+1]+cnt[k*2+2];
		}
	}

	int find(ll v){
		if(dp[0]<v)return -1;
		int k=0,l=0,r=N;
		ll sum=0;
		int cc=0;
		while(r-l>1){
			if(dp[k*2+2]>=v){
				l=(l+r)/2;
				k=k*2+2;
			}else{
				v-=dp[k*2+2];
				cc+=cnt[k*2+2];
				r=(l+r)/2;
				k=k*2+1;
			}
		}
		return cc+1;
	}
};

class segtree2{
public:
	static const int N=1<<17;
	ll dp[1<<18];
	segtree2(){
		for(int i=0;i<N*2;i++){
			dp[i]=INF;
		}
	}

	void update(int k,ll p){
		k+=N-1;
		dp[k]=p;
		while(k>0){
			k=(k-1)/2;
			dp[k]=min(dp[k*2+1],dp[k*2+2]);
		}
	}
	ll query(int a,int b,int k=0,int l=0,int r=N){
		if(r<=a || b<=l)return INF;
		if(a<=l && r<=b)return dp[k];
		int mid=(l+r)/2;
		ll vl=query(a,b,k*2+1,l,mid);
		ll vr=query(a,b,k*2+2,mid,r);
		return min(vl,vr);
	}
};


segtree seg;
segtree2 segsum;
segtree2 segsum2;

int n;
ll l;
ll a[100005],b[100005];
ll c[100005];

int main(void){
	scanf("%d%lld",&n,&l);
	for(int i=0;i<n;i++){
		scanf("%d%d",&a[i],&b[i]);
		if(a[i]-b[i]>0)dif.push_back(a[i]-b[i]);
		if(a[i]-b[i]>0)dif2.push_back(P(a[i]-b[i],i));
	}
	for(int i=0;i<n;i++){
		scanf("%lld",&c[i]);
	}
	sort(dif.begin(),dif.end());
	sort(dif2.begin(),dif2.end());
	ll sum=0;
	for(int i=0;i<dif.size();i++){
		sum+=dif[dif.size()-1-i]-c[i];
		//printf("sum %lld\n",sum);
		segsum.update(i,sum);
		if(i+1<dif.size()){
			segsum2.update(i,sum+dif[dif.size()-2-i]);
		}
	}
	for(int i=0;i<n;i++){
		if(a[i]-b[i]>0){
			int v=lower_bound(dif2.begin(),dif2.end(),P(a[i]-b[i],i))-dif2.begin();
			seg.update(v,P(1,a[i]-b[i]));
		}
	}
	int ans=n+1;
	for(int i=0;i<n;i++){
		ll rest=l-a[i];
		if(rest<=0){
			ans=1;
		}else{
			int v=lower_bound(dif2.begin(),dif2.end(),P(a[i]-b[i],i))-dif2.begin();
			if(a[i]-b[i]>0)seg.update(v,P(-1,-a[i]+b[i]));
			int co=seg.find(rest);
			if(a[i]-b[i]>0)seg.update(v,P(1,a[i]-b[i]));
			if(co==-1)continue;
			v=lower_bound(dif.begin(),dif.end(),a[i]-b[i])-dif.begin();
			v=dif.size()-1-v;
			if((a[i]-b[i]<=0 && segsum.query(0,co)>0) || (a[i]-b[i]>0 && segsum.query(0,min(v,co))>0 && segsum2.query(v,co)>a[i]-b[i])){
				//printf("%d %d %lld %lld %lld\n",i,co,rest,segsum.query(0,min(v,co)),segsum2.query(v,co));
				ans=min(ans,co+1);
			}
		}
	}
	printf("%d\n",ans==(n+1)?-1:ans);
	return 0;
}