Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include <sstream>
#include <fstream>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <utility>
#include <cassert>
#include <bitset>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define per(i,x,n) for(int i=n-1;i>=x;i--)
using namespace std;
#define ll long long
//head
int n, L;
int l, r, mid;
struct Bottle {
    int up, down, val;
    bool operator < (const Bottle a)const {
        return val > a.val;
    }
} a[100005];
ll b[100005], c[100005], sum[100005];
bool check(int x) {
    x--;
    rep(k, 1, n + 1) {
        if(c[k] <= x)
            continue;
        ll p = L - a[k].up, go = 0;
        if(k <= x && sum[x + 1] - a[k].val >= p)
            return 1;
        if(k > x && sum[x] >= p)
            return 1;
    }
    return 0;
}
inline char gc() {
    static char buf[1<<20], *head = buf, *tail = buf;
    return (head == tail && (tail = (head = buf) + fread(buf, 1, 1 << 20, stdin), head == tail)? -1: *head++);
}
template <typename T> inline bool read(T &x) {
    static bool f;
    static char c;
    for (c = gc(), f = false; !isdigit(c); c =gc()) {
        if (c == EOF)
            return false;
        else if (c == 45)
            f = true;
    }
    for (x = 0; isdigit(c); c = gc())
        x = x * 10 + c - 48;
    if (f)
        x = -x;
    return true;
}
int main() {
    read(n);read(L);
    rep(i, 1, n + 1)read(a[i].up),read(a[i].down),a[i].val = a[i].up - a[i].down;
    rep(i, 1, n + 1)read(b[i]);
    sort(a + 1, a + n + 1);
    rep(i, 1, n + 1)sum[i] = sum[i - 1] + a[i].val;
    ll cnt = 1, dis = 0;
    rep(i, 2, n + 1) {
        dis += (a[i].val - b[cnt]);
        if(dis <= 0)
            break;
        cnt++;
    }
    c[1] = cnt;
    int k = 2;
    for(; k <= n; k++) {
        if(cnt < k - 1 || cnt == n)
            break;
        dis += (a[k - 1].val - a[k].val);
        while(dis > 0 && cnt < n)
            cnt++, dis += (a[cnt + 1].val - b[cnt]);
        c[k] = cnt;
    }
    for(; k <= n; k++)
        c[k] = cnt;
    int day = 1;
    for(int i = 1; a[i].val > 0 && i <= n; i++, day++);
    l = 1, r = day;
    while(l < r) {
        mid = (l + r) / 2;
        if(check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    if(check(l))
        cout << l << endl;
    else
        cout << -1 << endl;
    return 0;
}