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 <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5, INF = 0x3f3f3f3f;

struct P
{
	ll dif; int id;
	P(ll dif = 0, int id = -1) :dif(dif), id(id) {}
	P operator + (const P &a) const { return P(dif + a.dif, id); }
	bool operator < (const P &a) const { return dif > a.dif; }
};

P p[N];
int n, ans, loc[N];
ll L, a[N], b[N], c[N], d[N];

ll ok(int mid, int i)
{
	if (i <= mid) return p[mid].dif - a[p[i].id] + b[p[i].id];
	return p[mid].dif;
}

int main()
{
	while (~scanf("%d%lld", &n, &L))
	{
		for (int i = 0; i < n; i++)
		{
			scanf("%lld%lld", &a[i], &b[i]);
			p[i] = P(a[i] - b[i], i);
		}
		for (int i = 0; i < n; i++)
		{
			scanf("%lld", &c[i]);
			if (i) c[i] += c[i - 1];
		}
		sort(p, p + n);
		for (int i = 0; i < n; i++)
			loc[p[i].id] = i;
		int fu = n - 1;
		for (; fu >= 0 && p[fu].dif <= 0; fu--);
		for (int i = 1; i < n; i++)
			p[i] = p[i] + p[i - 1];
		ans = INF;
		for (int i = 0; i < n; i++)
		{
			ll len = L - a[i];
			int l = -1, r = fu;
			if (len <= 0) { ans = min(ans, 1); continue; }
			while (r - l > 1)
			{
				int mid = l + r >> 1;
				if (ok(mid, loc[i]) < len) l = mid;
				else r = mid;
			}
			int now = r - (r >= loc[i]), v = ok(r, loc[i]);
			if (v >= len&& v > c[now])
				ans = min(ans, now + 2);
		}
		printf("%d\n", ans == INF ? -1 : ans);
	}
	return 0;
}