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;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll N,L;
vector<P> a;
ll D[100010],C[100010];
ll l[100010];
ll mx;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin>>N>>L;
  rep(i,N){
    ll A,B;
    cin>>A>>B;
    a.push_back(P(A,B));
  }
  sort(all(a),[](const P& b,const P& c){ return b.fi-b.se > c.fi-c.se; });
  rep(i,N)D[i+1]=max(0LL,a[i].fi-a[i].se);
  rep(i,N)cin>>C[i+1];
  rep(i,N){
    C[i+1]+=C[i];
    D[i+1]+=D[i];
  }

  repl(i,1,N){
    ll lb=-1,ub=i+1;
    while(ub-lb>1){
      ll X=(lb+ub)/2;
      ll sum=D[i+1]-(D[X+1]-D[X]);
      if(sum>C[i])ub=X;
      else lb=X;
    }
    l[i]=ub;
    if(ub==i+1){
      l[i]=INF;
    }
  }
  l[0]=0;
  rep(i,N)maxch(l[i+1],l[i]);

  ll res=INF;
  rep(i,N){
    ll rest=L-a[i].fi;
    if(rest<=0){
      cout<<1<<endl;
      return 0;
    }
    if(D[i]>=rest){
      ll lb=-1,ub=i;
      while(ub-lb>1){
        ll X=(lb+ub)/2;
        if(D[X]>=rest)ub=X;
        else lb=X;
      }
      if(i<l[ub])continue;
      minch(res,ub+1);
    }else{
      ll lb=i+1,ub=N;
      while(ub-lb>1){
        ll X=(lb+ub)/2;
        if(D[i]+(D[X]-D[i+1])>=rest)ub=X;
        else lb=X;
      }
      if(i<l[ub]||(D[i]+(D[ub]-D[i+1]))<rest)continue;
      minch(res,ub);
    }
  }

  if(res==INF)cout<<-1<<endl;
  else cout<<res<<endl;

  return 0;
}