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
struct RMQ{
  int n;
  vector<int> dat;
  const int def=INT_MAX;
  RMQ(){}
  RMQ(int n_){init(n_);}
  RMQ(int n_,int *a){init(n_);construct(n_,a);}
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,def);
  }
  void construct(int n_,int *a){
    for(int i=0;i<n_;i++) dat[n-1+i]=a[i];
    for(int i=n-2;i>=0;i--) 
      dat[i]=min(dat[i*2+1],dat[i*2+2]);
  }
  void update(int k,int a){
    k+=n-1;
    dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
  }
  int query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return def;
    if(a<=l&&r<=b) return dat[k];
    int vl=query(a,b,k*2+1,l,(l+r)/2);
    int vr=query(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr);
  }
  int query(int a,int b){
    return query(a,b,0,0,n);
  }
};
#define MAX 114514
int n,l;
int a[MAX],b[MAX],c[MAX],d[MAX];
int sum[MAX],rev[MAX];
typedef pair<int,int> P;
vector<P> v;
signed main(){
  cin>>n>>l;
  for(int i=0;i<n;i++) cin>>a[i]>>b[i];
  for(int i=0;i<n;i++) cin>>c[i];
  for(int i=0;i<n;i++){
    if(a[i]>=l){
      cout<<1<<endl;
      return 0;
    }
  }
  for(int i=0;i<n;i++)
    v.push_back(P(a[i]-b[i],i));
  sort(v.begin(),v.end(),greater<P>());
  for(int i=0;i<n;i++)
    rev[v[i].second]=i;
  int ans=n+1;
  memset(sum,0,sizeof(sum));
  int cur=0,tmp=0,z=n,lim=n;
  bool dbg=0;
  for(int i=0;i<n;i++){
    if(v[i].first<0){
      z=i;
      break;
    }
    cur+=v[i].first;
    if(i) d[i-1]=cur-tmp;
    tmp+=c[i];
    sum[i]=cur;
    if(cur<=tmp) lim=min(lim,i);
    if(dbg) cout<<i<<" "<<cur<<" "<<tmp<<endl;
  }
  if(dbg) for(int i=0;i<z-1;i++) cout<<i<<" "<<d[i]<<endl;
  if(dbg) for(int i=0;i<z;i++) cout<<i<<":"<<sum[i]<<endl;
  //cout<<ans<<endl;
  RMQ rmq(z-1,d);
  for(int i=0;i<n;i++){
    {
      int x=l-a[i];
      int pos=lower_bound(sum,sum+z,x)-sum;
      if(pos==z) continue;
      if(pos>=lim) continue;
      if(dbg) cout<<i<<";"<<a[i]<<" "<<b[i]<<" "<<rev[i]<<endl;
      if(dbg) cout<<i<<";"<<x<<" "<<pos<<" "<<endl;
      if(rev[i]<=pos) continue;
      ans=min(ans,pos+2);
    }
  }
  for(int i=0;i<n;i++){
    {
      int x=l-b[i],y=a[i]-b[i];
      int pos=lower_bound(sum,sum+z,x)-sum;
      //cout<<pos<<endl;
      if(pos==z) continue;
      if(rmq.query(rev[i],pos)<=y) continue;
      if(dbg) cout<<i<<":"<<a[i]<<" "<<b[i]<<" "<<rev[i]<<endl;
      if(dbg) cout<<i<<":"<<x<<" "<<y<<" "<<pos<<" "<<rmq.query(rev[i],pos)<<endl;
      if(pos<=rev[i]) continue;
      ans=min(ans,pos+1);
    }
  }
  if(ans>n) ans=-1;
  cout<<ans<<endl;
  return 0;
}