Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

long long N, LL, A[100009], B[100009], C[100009], id[100009]; vector<pair<long long, long long>>X;
long long P1[100009], P2[100009], Q1[100009], Q2[100009];

long long sum(long long pos, long long XX) {
	if (pos < XX) return P1[pos];
	return P2[pos] - X[XX - 1].first;
}
long long query(long long pos, long long XX) {
	if (pos < XX) return Q1[pos];
	return min(Q1[XX - 1], Q2[pos] - X[XX - 1].first);
}

int main() {
	cin >> N >> LL;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> B[i]; id[i] = (1 << 30);
		if (A[i] - B[i] >= 1) X.push_back(make_pair(A[i] - B[i], i));
	}
	for (int i = 1; i <= N; i++) { cin >> C[i]; C[i] += C[i - 1]; }

	sort(X.begin(), X.end(), greater<pair<long long, long long>>());

	for (int i = 0; i < X.size(); i++) {
		id[X[i].second] = i + 1; P1[i + 1] = X[i].first; P2[i] = X[i].first;
		P1[i + 1] += P1[i]; if (i >= 1) P2[i] += P2[i - 1];
		Q1[i + 1] = P1[i + 1]; Q2[i] = P2[i];
	}
	for (int i = 1; i <= N; i++) { Q1[i] -= C[i]; Q2[i] -= C[i]; }
	Q1[0] = (1LL << 32); Q2[0] = (1LL << 32);
	for (int i = 1; i <= N; i++) { Q1[i] = min(Q1[i], Q1[i - 1]); Q2[i] = min(Q2[i], Q2[i - 1]); }

	long long ans = (1 << 30);

	for (int i = 1; i <= N; i++) {
		long long L = 0, R = X.size(), M, maxn = (1 << 30); if (id[i] == (1 << 30)) R++; R = min(R, N);
		for (int j = 0; j < 30; j++) {
			M = (L + R) / 2;
			long long ti = sum(M, id[i]);
			if (ti >= LL - A[i]) { R = M; maxn = min(maxn, M); }
			else { L = M; }
		}
		long long L2 = 0, R2 = X.size(), M2, maxn2 = -1; if (id[i] == (1 << 30)) R2++; R2 = min(R2, N);
		for (int j = 0; j < 30; j++) {
			M2 = (L2 + R2) / 2;
			long long rmq = query(M2, id[i]);
			if (rmq > 0) { maxn2 = max(maxn2, M2); L2 = M2; }
			else { R2 = M2; }
		}
		if (maxn2 < maxn) continue;
		ans = min(ans, maxn + 1);
	}
	if (ans == (1 << 30)) ans = -1;
	cout << ans << endl;
	return 0;
}