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;
const int N = 200005;
struct rec {
	int a,b,d;
};
int s[N],c[N],n,h;
rec a[N];
priority_queue<pair<int,int> > dui1,dui2;
bool cmp(const rec &a, const rec &b){
	return a.d > b.d;
}
int main(){
	scanf("%d%d",&n,&h);
	for (int i = 1; i <= n; i++){
		scanf("%d%d",&a[i].a,&a[i].b);
		a[i].d = a[i].a - a[i].b;
	}
	for (int i = 1; i <= n; i++)
		scanf("%d",&c[i]);
	s[0] = 0;
	for (int i = 1; i <= n; i++)
		s[i] = s[i - 1] + c[i];
	sort(a + 1,a + n + 1,cmp);
//	for (int i = 1; i <= n; i++)
//		printf("%d\n",a[i].d);
//	printf("!!!!\n");
	int len = 1;
	int p = 1;
	int s = 0;
	int ss = a[1].d;
	dui1.push(make_pair(a[1].b,1));
	for (int i = 2; i <= n; i++)
		dui2.push(make_pair(a[i].a,i));
//	printf("!!!!\n");
	while (len <= n){
		if (s > 0 || len == 1){
//			printf("!%d %d %d\n",len,p,s);
			while (! dui1.empty())
				if (dui1.top().second < p)
					dui1.pop();
				else break;
			if ((! dui1.empty()))
				if (dui1.top().first + ss >= h)
					break;
//			printf("!%d\n",len);
			while (! dui2.empty())
				if (dui2.top().second <= len)
					dui2.pop();
				else break;
			if ((! dui2.empty()))
				if (dui2.top().first - a[len].d + ss >= h)
					break;
		}
//		printf("!%d\n",len);
		len++;
		dui1.push(make_pair(a[len].b,len));
//		printf("!! %d\n",s);
		s += a[len].d - c[len - 1];
//		printf("!! %d %d %d %d\n",s,a[len].d,len,c[len - 1]);
		ss += a[len].d;
		while (s <= 0 && p < len){
			s += a[p].d - a[p + 1].d;
			p++;
		}
	}
//	printf("!!!!\n");
	if (len <= n) printf("%d\n",len);
	else printf("-1\n");
}