Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

constexpr ll inf = 1e18;

template<typename Monoid>
class segment_tree {
    using T = typename Monoid::type;

public:
    segment_tree(std::vector<T> const& init)
        : sz(init.size()), n(expand(init.size()))
    {
        dat.assign(n*2, Monoid::id());
        std::copy(begin(init), end(init), begin(dat) + n);
        for(int i = n - 1; i >= 0; --i) {
            dat[i] = Monoid::op(dat[i * 2], dat[i * 2 + 1]);
        }
    }

    segment_tree(int const n_, T const& init = Monoid::id())
        : segment_tree(std::vector<T>(n_, init))
    {}

    void update(int p, T val) {
        assert(0 <= p && p < sz);
        dat[p += n] = val;
        while(p /= 2) {
            dat[p] = Monoid::op(dat[p * 2], dat[p * 2 + 1]);
        }
    }

    // [l, r)
    T query(int l, int r) const {
        assert(0 <= l && l <= r && r <= sz);
        l += n, r += n;
        T res1 = Monoid::id(), res2 = Monoid::id();
        while(l != r) {
            if(l & 1) res1 = Monoid::op(res1, dat[l++]);
            if(r & 1) res2 = Monoid::op(dat[--r], res2);
            l /= 2, r /= 2;
        }
        return Monoid::op(res1, res2);
    }

private:
    int expand(int n_) const {
        assert(n_ >= 1);
        return n_ == 1 ? n_ : expand((n_ + 1) / 2) * 2;
    }

private:
    const int sz, n;
    std::vector<T> dat;
};

struct RSMQ {
    struct type {
        ll sum, mini, maxi;
        type() : sum(0), mini(inf), maxi(-inf) {}
        type(ll s, ll mi, ll ma) : sum(s), mini(mi), maxi(ma) {}
    };
    static type id() {
        return type{0, inf, -inf};
    }
    static type op(type const& l, type const& r) {
        if(l.mini == inf) return r;
        if(r.mini == inf) return l;
        return type(l.sum + r.sum,
                    min(l.mini, l.sum + r.mini),
                    max(l.maxi, l.sum + r.maxi));
    }
};

int main() {
    ll n, l; cin >> n >> l;
    vector<pll> drink(n);
    vector<ll> c(n);
    for(int i = 0; i < n; ++i) {
        cin >> drink[i].first >> drink[i].second;
    }
    for(int i = 0; i < n; ++i) {
        cin >> c[i];
    }
    sort(begin(drink), end(drink), [] (const pll& p1, const pll& p2) {
        return p1.first - p1.second > p2.first - p2.second;
    });

    // a[i] - b[i], a[i] - b[i] - c[i], a[i] - b[i] - c[i - 1]
    vector<RSMQ::type> dat1(n), dat2(n), dat3(n);
    for(int i = 0; i < n; ++i) {
        const ll a = drink[i].first, b = drink[i].second;
        dat1[i] = RSMQ::type{a - b, a - b, a - b};
        dat2[i] = RSMQ::type{a - b - c[i], a - b - c[i], a - b - c[i]};
        if(i != 0) {
            dat3[i] = RSMQ::type{a - b - c[i - 1], a - b - c[i - 1], a - b - c[i - 1]};
        }
    }
    segment_tree<RSMQ> seg1(dat1), seg2(dat2), seg3(dat3);

    int ans = n + 1;
    for(int i = 0; i < n; ++i) { // last use
        const ll r = l - drink[i].first;
        if(r <= 0) {
            ans = 1;
            break;
        }
        if(seg1.query(0, i).maxi < r) {
            if(seg2.query(0, i).mini < 0) continue;
            int lb = i + 1, ub = n;
            const ll s = seg1.query(0, i).sum;
            while(ub - lb > 1) {
                const int mid = (ub + lb) >> 1;
                (seg1.query(i + 1, mid).maxi < r - s ? lb : ub) = mid;
            }
            if(seg1.query(i + 1, ub).maxi < r - s) continue;
            if(seg2.query(0, i).sum + seg3.query(i + 1, ub).mini <= 0) continue;
            ans = min(ans, ub);
        } else {
            int lb = 0, ub = i;
            while(ub - lb > 1) {
                const int mid = (lb + ub) >> 1;
                (seg1.query(0, mid).maxi < r ? lb : ub) = mid;
            }
            if(seg2.query(0, ub).mini <= 0) continue;
            ans = min(ans, ub + 1);
        }
    }

    cout << (ans == n + 1 ? -1 : ans) << endl;
}