Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include<iostream>
#include<algorithm>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define per(i,x,n) for(int i=n-1;i>=x;i--)
using namespace std;
#define ll long long
//head
int n,L;
int l,r,mid;
struct Bottle
{
    int up,down,val;
    bool operator < (const Bottle a)const
    {
        return val>a.val;
    }
}a[100005];
ll b[100005],c[100005],sum[100005];
bool check(int x)
{
    x--;
    rep(k,1,n+1)
     {
         if(c[k]<=x)continue;
        ll p=L-a[k].up,go=0;
        if(k<=x&&sum[x+1]-a[k].val>=p)return 1;
        if(k>x&&sum[x]>=p)return 1;
    }
    return 0;
}
int main()
{
     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     int mx=0;
     cin>>n>>L;
     rep(i,1,n+1)cin>>a[i].up>>a[i].down,a[i].val=a[i].up-a[i].down,mx=max(a[i].val,mx);
     if(mx>=L){cout<<1<<endl;return 0;}
     rep(i,1,n+1)cin>>b[i];
     sort(a+1,a+n+1);
     rep(i,1,n+1)sum[i]=sum[i-1]+a[i].val;
     ll cnt=1,dis=0;
     rep(i,2,n+1)
     {
         dis+=(a[i].val-b[cnt]);
         if(dis<=0)break;cnt++;
     }
     c[1]=cnt;
     int k=2;
     for(;k<=n;k++)
     {
         if(cnt<k-1||cnt==n)break;
         dis+=(a[k-1].val-a[k].val);
         while(dis>0&&cnt<n)cnt++,dis+=(a[cnt+1].val-b[cnt]);c[k]=cnt;
     }
     for(;k<=n;k++)c[k]=cnt;
     int day=n;rep(i, 1, n+1)if(a[i].val<=0){day=i;break;}//for(int i=1;a[i].val>0&&i<=n;i++,day++);
     l=1,r=day;
     if(l>r){cout<<-1<<endl;return 0;}
     while(l<r)
     {
         mid=(l+r)/2;
         if(check(mid))r=mid;
         else l=mid+1;
     }
     if(check(l))cout<<l<<endl;
     else cout<<-1<<endl;
     return 0;
}