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;
 
typedef long long ll;
#define MAX 100005
typedef pair<ll,ll> P;
typedef pair<ll, P > PP;
 
const ll INF = 10000000000000000LL;
 
struct segtree {
  vector<ll> data;
  vector<ll> delay;
 
  int n;
  void init(int _n){
    n = 1;
    while( n < _n ) n*=2;
    data.resize( 2 * n );
    delay.resize( 2 * n );
  }
 
  void delaycalc( int k ){
    data[k] = data[k] + delay[k];
    if( k + 1 < n )
      for(int i=1;i<=2;i++)
        delay[ 2 * k + i ] += delay[k];
    delay[k] = 0;
  }
 
  void add( int a, int b, ll x, int k, int l, int r ){
    delaycalc( k );
    if( r<=a  || b<=l ) return;
 
    else if( a <= l && r <= b ) {
      delay[k] = x;
      delaycalc( k );
    } else {
      add( a, b, x, 2 * k + 1, l, (l+r)/2 );
      add( a, b, x, 2 * k + 2, (l+r)/2, r );
      data[k] = min( data[ 2 * k + 1 ], data[ 2 * k + 2 ] );
    }
  }
 
  ll query( int a,int b,int k,int l, int r ){
    delaycalc( k );
    if( r<=a  || b<=l ) return INF;
    else if( a <= l && r <= b ) {
      return data[k] + delay[k];
    } else {
      ll vl = query( a, b, 2 * k + 1, l, (l + r)/2 );
      ll vr = query( a, b, 2 * k + 2, (l + r)/2, r );
      return min( vl, vr );
    }      
  }
 
  //[a, b)
  void add( int a, int b, ll x ,bool flg=false){
    if(flg)x*=-1LL;
    add( a, b, x, 0, 0, n );
  }
  //[a, b )
  ll query( int a, int b ,bool flg=false){
    ll res=query( a, b, 0, 0, n );
    if(flg)res*=-1LL;
    return res;
  }
  
};
 
 
segtree S,T;
ll N,L;
ll a[MAX],b[MAX];
ll c[MAX];
 
int search(ll x){
  int L=0,R=N,M;
  while(L<R){
    M=(L+R)/2;
    if(S.query(0,M,true) <x )L=M+1;
    else R=M;
  }
  return L;
}
 
int main(){
  cin>>N>>L;
  S.init(N+10);
  T.init(N+10);
 
  vector<PP> v;
  for(int i=0;i<N;i++){
    cin>>a[i]>>b[i];
    if(a[i]>=L){
      cout<<1<<endl;
      return 0;
    }
    v.push_back(PP(a[i]-b[i],P(a[i],b[i])));
  }
  sort(v.begin(),v.end());
  reverse(v.begin(),v.end());
  for(int i=0;i<N;i++){
    a[i]=v[i].second.first;
    b[i]=v[i].second.second;
  }
  for(int i=0;i<N;i++){
    ll num;
    cin>>num;
    c[i]=num;
    T.add(i,N,-num);
    T.add(i,N,a[i]-b[i]);
    S.add(i,N,a[i]-b[i],true);
  }
  
  ll ans=INF;
  for(int i=N-1;i>=0;i--){
    S.add(i,N,b[i]-a[i],true);
    T.add(i,N,b[i]-a[i]);
    if(i<N-1){
      T.add(i,N,c[i]);
      T.add(i+1,N,-c[i]);
    }
    /*    
    for(int j=0;j<N;j++){
      cout<<S.query(j,j+1,true)<<' '<<T.query(j,j+1)<<endl;
    }
    cout<<endl<<endl;
    */
    int id=search( L-a[i] );
 
 
    int si=0;
    if(i==0)si=1;
    if( T.query(si,id) > 0  && S.query(0,id,true) >= L-a[i] ){
      if(i<id)id--;
      ans=min(ans,(ll)id+1);
    }
 
    S.add(i,N,a[i]-b[i],true);
    T.add(i,N,a[i]-b[i]);
  }
  if(ans==INF)ans=-1;
  cout<<ans<<endl;  
  return 0;
  
}