Let \(D_i = A_i - B_i\). In fact, the following greedy algorithm is optimal: perform exchanges as many times as possible in ascending order of \(D_i\). More specifically, the following algorithm is valid:

• Let \(\mathrm{ans}=0\).
• While there exists \(i\) with \(N\geq A_i\), repeat the following:
  • Take \(i\) with the minimum \(D_i\) among those with \(N\geq A_i\). (Take any of them if there are multiple such indices.) Set \(N\leftarrow N-A_i+B_i\) (or subtract \(D_i\) from \(N\)), and add \(1\) to \(\mathrm{ans]\).

However, in this problem \(N\) can be up to \(10^{18}\), so this algorithm cannot be directly applied. Instead, we modify the algorithm as follows.

• Let \(\mathrm{ans}=0\).
• Rearrange \(A\) and \(B\) to make \(D_1 \leq D_2\leq \dots \leq D_M\).
• For \(i=1,2,\dots,M\) in order:
  • Let \(x\) be the maximum number of operations applied for this \(i\). Namely, let \(x=\max\left\{0, \left\lfloor\frac{N-A_i}{D_i}\right\rfloor+1\right\}\). Subtract \(D_i\times x\) from \(N\), and add \(x\) to \(\mathrm{ans}\).

The computational complexity is \(O(M\log M)\), where the initial sorting is bottleneck.

Sample code (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;
}