Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int,int> P;
typedef unsigned int ui;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
LP x[100000]; ll csum[100000]; ll c[100000]; ll sum[100000];
ll dif1[100000] = {};
int m; ll dat[399999];
void init(int m_) {
	m = 1;
	while (m < m_)m *= 2;
	rep(i, 2 * m - 1)dat[i] = INF;
}
void updat(int k,ll a) {
	k += m - 1; dat[k] = a;
	while (k > 0) {
		k = (k - 1) / 2;
		dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
	}
}
ll query(int a, int b, int k, int l, int r) {
	if (r <= a || b <= l)return INF;
	if (a <= l && r <= b)return dat[k];
	else {
		ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
}
int main() {
	int n;
	ll l; cin >> n >> l; m = n - 1;
	rep(i, n) {
		ll a, b; cin >> a >> b;
		x[i] = { a - b,a };
	}
	rep(i, n) {
		cin >> c[i];
	}
	sort(x, x + n,greater<LP>());
	sum[0] = x[0].first;
	csum[0] = c[0];
	int chk = n;
	Rep(i, 1, n) {
		sum[i] = sum[i - 1] + x[i].first;
		if (x[i].first <= 0)chk = i;
		csum[i] = csum[i - 1] + c[i];
	}
	dif1[0] = sum[0] - csum[0];
	Rep(i,1, n) {
		dif1[i] = min(dif1[i - 1], sum[i] - csum[i]);
	}
	init(m);
    rep(i, n - 1) {
		updat(i,sum[i + 1] - csum[i]);
	}
	int out = (int)MOD;
	rep(i, n) {
		ll nx = x[i].first; ll ny = x[i].second;
		int loc = lower_bound(sum, sum + chk, l - ny) - sum;
		if (loc == chk)continue;
		if (loc < i) {
			if (dif1[loc]>0)out = min(out, 2 + loc);
		}
		else {
			loc = lower_bound(sum, sum + chk, l - ny + nx) - sum;
			if (loc == chk)continue;
			ll mi = query(i, loc, 0, 0, m);
			if (mi-nx>0)out = min(out, loc + 1);
		}
	}
	if (out == (int)MOD) {
		cout << -1 << endl;
	}
	else {
		cout << out << endl;
	}
	return 0;
}