\(D\) 日目時点でのゴミはちょうど \(C\) kg であるとしてよいです (\(C\) 未満ならば、\(X\) を適切に増やすことでちょうど \(C\) kg にできます) 。\(D\) 日目から順に日程を逆から見ていくことを考えると、以下のような問題に言い換えられます。

• \(1\) 日目の朝にゴミが \(C\) kg ある。\(1\) 日あたり \(1\) kg ゴミが減っていく。
• \(i = 1, \dots, N\) について、\(d_i\) 日目にはゴミを \(a_i\) kg 増やす操作を \(0\) 回または \(1\) 回行える。
• 途中でゴミが \(0\) kg 未満にならずに \(D\) 日目に至るためには、操作を最小で合計何回行えばよいか？

これは、\(a_i\) の大きい順に操作を貪欲に選ぶことで解くことができます。具体的には以下の手順を行えばよいです。なお、便宜上 \(d_{N+1} = D, a_{N+1} = 0\) とします。

• 整数を大きい順に取り出せるヒープ \(H\) を用意する。はじめ、\(H\) は空である。
• \(i = 1, \dots, N+1\) の順に、次の処理を行う。
  • \(C \lt d_i\) である間、「\(H\) から最大の整数を取り出して \(C\) に加える」ことを繰り返す。途中で \(H\) が空になったら \(-1\) を出力する。
  • \(H\) に \(a_i\) を追加する。
• \(H\) から整数を取り出した回数の合計が答えとなる。

実装例 (C++) :

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

int main() {
    int n, c, d;
    cin >> n >> c >> d;
    vector<pair<int, int>> event(n);
    for (auto& [x, y] : event) {
        cin >> x >> y;
        x = d - x;
    }
    reverse(begin(event), end(event));
    event.emplace_back(d - 1, 0);
    priority_queue<int> heap;
    int answer = 0;
    for (const auto& [x, y] : event) {
        while (c < x) {
            if (heap.empty()) {
                cout << -1 << '\n';
                return 0;
            }
            answer += 1;
            c += heap.top();
            heap.pop();
        }
        heap.push(y);
    }
    cout << answer << '\n';
    return 0;
}