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 int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
int INF=1001001001001001001ll;
struct segtree{
    static const int SEG=1<<17;
    vint dat;
    segtree():dat(SEG*2,INF){}
    void update(int k,int x){
        k+=SEG-1;
        dat[k]=x;
        while(k){
            k=(k-1)/2;
            dat[k]=min(dat[k*2+1],dat[k*2+2]);
        }
    }
    int query(int a,int b,int k=0,int l=0,int r=SEG){
        if(r<=a||b<=l)return INF;
        if(a<=l&&r<=b)return dat[k];
        return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
    }
};
 
int N,L;
int A[100000],B[100000];
int C[100000];
 
int premin[111111];
int sufmax[111111];
 
int SA[111111];
int SC[111111];
signed main(){
    scanf("%lld%lld",&N,&L);
    rep(i,N)scanf("%lld%lld",&A[i],&B[i]);
    rep(i,N)scanf("%lld",&C[i]);
    rep(i,N)SC[i+1]=SC[i]+C[i];
    vpint vec;
    rep(i,N)vec.pb(pint(B[i]-A[i],B[i]));
    sort(all(vec));
    rep(i,N){
        A[i]=-vec[i].fi+vec[i].se;
        B[i]=vec[i].se;
    }
    rep(i,N)SA[i+1]=SA[i]+A[i]-B[i];
 
    sufmax[N]=-1001001001;
    for(int i=N-1;i>=0;i--){
        sufmax[i]=max(sufmax[i+1],A[i]);
    }
    premin[0]=1001001001;
    for(int i=1;i<=N;i++){
        premin[i]=min(premin[i-1],SA[i]-SC[i]);
    }
 
 
    int ans=INF;
    for(int i=0;i<N;i++){
        if(premin[i]<=0)break;
        if(SA[i]+sufmax[i]>=L)chmin(ans,i+1);
    }
 
 
    deque<pint>Bs;
    deque<pint>As;
    for(int i=1;i<=N;i++){
        if(A[i-1]-B[i-1]<=0)break;
        while(Bs.size()&&Bs.back().fi<=B[i-1])Bs.pop_back();
        Bs.pb(pint(B[i-1],i-1));
        while(Bs.size()>1&&Bs[1].fi+SA[i]>=L)Bs.pop_front();
 
        int t=Bs.front().se;
        if(B[t]+SA[i]<L)continue;
        if(premin[t]<=0)continue;
 
        while(As.size()&&As.back().fi>=SA[i]-SC[i-1])As.pop_back();
        As.pb(pint(SA[i]-SC[i-1],i-2));
        while(As.size()&&As.front().se<t)As.pop_front();
        if(As.size()&&As.front().fi-(A[t]-B[t])<=0)continue;
        chmin(ans,i);
    }
 
    if(ans!=INF)cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}