\(D_i = A_i - B_i\) と定義します。実は、\(D_i\) の小さい順に使えるだけ使う貪欲法が最適です。具体的には以下のアルゴリズムは正当です。

• \(\mathrm{ans}=0\) とする。
• \(N\geq A_i\) であるような \(i\) が存在する限り、以下を繰り返し行う。
  • \(N\geq A_i\) であるような \(i\) のうち \(D_i\) が最小であるもの（複数あるならばそのうちの一つ）を選ぶ。\(N\leftarrow N-A_i+B_i\) と更新し（あるいは \(N\) から \(D_i\) を引き）、\(\mathrm{ans}\) に \(1\) を足す。

しかし本問題では \(N\) は最大で \(10^{18}\) と大きいため、このアルゴリズムをそのまま用いることはできません。そこで以下のようにアルゴリズムを修正します：

• \(\mathrm{ans}=0\) とする。
• \(D_1 \leq D_2\leq \dots \leq D_M\) となるように \(A,B\) を並び替える。
• \(i=1,2,\dots,M\) の順に以下を行う。
  • この \(i\) に対して連続して操作を行える回数の最大値を \(x\) とする。具体的には、\(x=\max\left\{0, \left\lfloor\frac{N-A_i}{D_i}\right\rfloor+1\right\}\) とする。\(N\) から \(D_i\times x\) を引き、\(\mathrm{ans}\) に \(x\) を足す。

計算量は最初のソートがボトルネックとなり \(O(M\log M)\) です。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    ll n;
    int m;
    cin >> n >> m;
    vector<tuple<ll, ll, ll>> ls;
    for (int i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        ll d = a - b;
        ls.emplace_back(d, a, b);
    }
    sort(ls.begin(), ls.end());
    ll ans = 0;
    for (auto [d, a, b]: ls) {
        if (a > n) continue;
        ll x = (n - a) / d + 1;
        ans += x;
        n -= x * d;
    }
    cout << ans << endl;
}