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
ll n, L ,need;
ll l, r, mid;
struct Bottle {
    ll up, down, val;
    bool operator < (const Bottle a)const {
        return val > a.val;
    }
} a[100005];
ll b[100005], c[100005], sum[100005];
int main()
{
     ios::sync_with_stdio(false);cin.tie(0);cout.tie(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;
     rep(i,1,n+1)cin>>b[i],c[i]=c[i-1]+b[i];         //c[i]保存b的前缀和
     sort(a+1,a+n+1);
     rep(i,1,n+1)sum[i]=sum[i-1]+a[i].val;               //sum[i]保存a的前缀和
    ll day = 1;for(int i=1;a[i].val>0&&i<=n;i++,day++);    //找到可能的答案范围
     ll ans=999999999;        //保存答案
     rep(k,1,n+1)
     {
         l=1,r=day;
         need=L-a[k].up;
         while(l<r)
         {
             ll mid=(l+r)>>1;
             if(mid==1)l=mid+1;
             else if((mid-1)>=k&&sum[mid]-a[k].val<=c[mid-1])r=mid;
             else if((mid-1)<k&&sum[mid-1]<=c[mid-1])r=mid;
              else l=mid+1;
         }      //求出k作为最后一瓶饮料使用时最少需要多少天被追上，复杂度为logr
         l=1;
         while(((r-1)>=k&&sum[r]-a[k].val<=c[r-1])||((r-1)<k&&sum[r-1]<=c[r-1]))
         r--;     //判断第r天前是否被追上
         ll vis=0;
        while(l<r)
        {
            ll mid=(l+r)>>1;
            if((mid-1)>=k&&sum[mid]-a[k].val>=need){r=mid;vis=mid;}
             else if((mid-1)<k&&sum[mid-1]>=need){r=mid;vis=mid;}
              else l=mid+1;
        }     //求出最少所用天数复杂度为logr
        if(((l-1)>=k&&sum[l]-a[k].val>=need)||((l-1)<k&&sum[l-1]>=need))
        ans=min(l,ans);
        else if(vis)
        ans=min(vis,ans);
     }
     if(ans==999999999)cout<<-1<<endl;
     else cout<<ans<<endl;
     return 0;
}