Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cassert>
#include <numeric>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#define rep(i, n) for (int i = 0; i < n; i++)
// #define show(x) cerr << #x << " = " << x << endl
#define show(x)

using namespace std;
using ll = long long;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

constexpr ll INF = 1LL << 60;
constexpr int SIZE = 1 << 17;
struct Seg {
    int n_;
    ll dat[2 * SIZE - 1];
    Seg(const int x)
    {
        n_ = 1;
        while (n_ < x) {
            n_ *= 2;
        }
        rep(i, 2 * n_ - 1)
        {
            dat[i] = INF;
        }
    }

    void update(int k, ll a)
    {
        k += n_ - 1;
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
        }
    }

    ll query(int a, int b, int k, int l, int r)
    {
        if (r <= a or b <= l) {
            return INF;
        }
        if (a <= l and r <= b) {
            return dat[k];
        } else {
            ll vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
            ll vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }
    ll query(int a, int b)
    {
        return query(a, b, 0, 0, n_);
    }
};

struct Data {
    ll A;
    ll B;
    ll Total;
    bool operator>(const Data& d) const
    {
        return (Total != d.Total) ? Total > d.Total : A < d.A;
    }
};
ostream& operator<<(ostream& os, const Data& d)
{
    os << d.A << " " << d.B << " " << d.Total << endl;
    return os;
}

int main()
{
    ll N;
    ll L;
    cin >> N >> L;
    vector<Data> data(N);
    for (ll i = 0; i < N; i++) {
        ll A, B;
        cin >> A >> B;
        data[i] = Data{A, B, A - B};
    }
    sort(data.begin(), data.end(), greater<Data>{});
    vector<ll> accum(N + 1, 0);
    for (ll i = 1; i <= N; i++) {
        accum[i] = max(data[i - 1].Total, 0LL);
    }
    for (ll i = 1; i <= N; i++) {
        accum[i] += accum[i - 1];
    }

    //    cerr << accum << endl;

    vector<ll> C(N);
    for (ll i = 0; i < N; i++) {
        cin >> C[i];
    }

    vector<ll> sum1(N + 1, 0);
    for (ll i = 1; i <= N; i++) {
        sum1[i] = data[i - 1].Total - C[i - 1];
    }
    for (ll i = 1; i <= N; i++) {
        sum1[i] += sum1[i - 1];
    }

    vector<ll> sum2(N + 1, 0);
    for (ll i = 2; i <= N; i++) {
        sum2[i] = data[i - 1].Total - C[i - 2];
    }
    for (ll i = 1; i <= N; i++) {
        sum2[i] += sum2[i - 1];
    }

    Seg seg1(N + 1);
    Seg seg2(N + 1);
    for (ll i = 0; i <= N; i++) {
        seg1.update(i, sum1[i]);
    }
    for (ll i = 0; i <= N; i++) {
        seg2.update(i, sum2[i]);
    }

    //    cerr << data << endl;
    // show(sum1);
    // show(sum2);
    //    show(accum);
    // show(data);
    constexpr ll INF = 1LL << 60;
    ll minimum = INF;


    for (ll i = 0; i < N; i++) {
        show(i);
        ll goal = L - data[i].A;
        const ll lower = lower_bound(accum.begin(), accum.end(), goal) - accum.begin();
        if (lower <= i) {
            show("hogeohoegoeodwqd");
            show(goal);
            show(lower);
            const ll mini = seg1.query(1, lower + 1);
            show(mini);
            if (mini <= 0) {
                continue;
            } else {
                minimum = min(minimum, lower + 1);
            }
        } else {
            show("feffwuefwiuefwuef");
            // if (lower >= N) {
            //     continue;
            // }
            goal = L - data[i].B;
            const ll lower = lower_bound(accum.begin(), accum.end(), goal) - accum.begin();
            if (lower >= N + 1) {
                //          cerr << accum[N] - goal << endl;
                continue;
            }
            show(lower);
            if (i == 0) {
                show("i=0");
                const ll mini = seg2.query(2, lower + 1);
                show(mini);
                if (mini <= 0) {
                    continue;
                } else {
                    minimum = min(minimum, lower);
                }
            } else {
                show("i!=0");
                const ll mini1 = seg1.query(1, i + 1);
                show(mini1);
                if (mini1 <= 0) {
                    continue;
                }
                if (i == N - 1) {
                    minimum = min(minimum, lower);
                } else {
                    const ll mini2 = seg2.query(i + 2, lower + 1) - sum2[i + 1];
                    show(mini2);
                    if (sum1[i] + mini2 <= 0) {
                        continue;
                    }
                    minimum = min(minimum, lower);
                }
            }
        }
    }
    cout << ((minimum == INF) ? -1 : minimum) << endl;

    return 0;
}