Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const int mod=1000000007 ;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

int main(void){
	cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);
	int n,i;cin>>n;
	llint L;cin>>L;
	vector<pair<llint,llint>>dri(n);//通常の登り,ピーク登り
	vector<llint>c(n+1);//相手
	for(i=0;i<n;i++){llint AA,BB;cin>>AA>>BB;dri[i]=mp(AA-BB,AA);}
	for(i=0;i<n;i++){cin>>c[i+1];c[i+1]+=c[i];}
	SO(dri);REV(dri);
	vector<llint>wa(n+1);
	for(i=0;i<n;i++){wa[i+1]=wa[i]+max(0LL,dri[i].fir);}
	vector<llint>yorui(n+1);
	yorui[0]=big;yorui[1]=big;
	for(i=2;i<=n;i++){yorui[i]=wa[i]-c[i-1];mineq(yorui[i],yorui[i-1]);}
	llint usedD=-big;
	int outm=1,ans=mod;
	while(outm<n&&wa[outm]>c[outm]){outm++;}
	//cerr<<"outm="<<outm<<endl;
	//for(i=0;i<n;i++){cerr<<yorui[i]<<" ";}cerr<<endl;
	for(i=n-1;i>=0;i--){
		
		if(!maxeq(usedD,dri[i].sec)){continue;}
		//最終日使用ドリンク
		llint Lg=L-dri[i].sec;
		//cerr<<"Lg="<<Lg<<endl;
		if(wa[i]>=Lg){//それまでに普通に足りている
			int bas=LBI(wa,Lg);
			//cerr<<"i="<<i<<"bass="<<bas<<endl;
			if(bas<outm){mineq(ans,bas+1);}
		}else{
			if(outm<=i){continue;}
			int bas=LBI(wa,Lg+max(0LL,dri[i].fir));
			if(bas==n+1){continue;}
			//cerr<<"i="<<i<<"bas="<<bas<<endl;
			if(yorui[bas]>dri[i].fir){mineq(ans,bas);}
		}
	}
	if(ans==mod){ans=-1;}
	cout<<ans<<endl;
	return 0;
}
/*
7 10
4 7
1 6
-3 4
-4 10
*/