\(D_i=A_i-B_i\)、\(K=\max_i A_i\) と定義します。

まず、\(A_i\) の値が等しい \(i\) が複数存在する場合、そのうち \(B_i\) が最大であるもの（の一つ）以外は使うメリットがないため、削除してしまって問題ありません。これにより、\(M\leq K\) とすることができます。

問題を整理して逆から捉えると、以下のようになります：

• 最初、スコアは \(N\) である。
• 好きな整数 \(x\ (0\leq x\leq N)\) を選ぶ。その後、以下を繰り返し行う。
  • \(x\geq B_i\) かつ \(x+D_i\leq N\) であるような \(i\) を選んで、\(x\) に \(D_i\) を加算し、スコアに \(B_i\) を加算する。
• スコアの最大値を求めよ。

これは重み \(D_i\)、価値 \(B_i\)、容量 \(N\) の個数制限なしナップサック問題に近く（実際 \(x\geq K\) となったあとは完全にナップサック問題と一致します）、通常のナップサック問題にも用いられるテクニックを使って解くことができます。以下ナップサック問題に準えて、ある \(i\) に対して一回操作を行うことを、アイテム \(i\) を一つ用いる、と表現します。

\(\frac{B_i}{D_i}\) の値が最大であるような \(i\) (の一つ) を \(i'\) とおきます。実は、アイテム \(i'\) 以外で使用したアイテムに対する \(D_i\) の総和（同じアイテムを複数回用いた場合複数回カウントする）が \(K(K+1)\) 未満であるような最適解が存在することが示せます。

よって、\(x<K(K+1)\) の範囲内では通常のナップサック問題と同様の DP を行ったのち、それ以降についてはアイテム \(i'\) を使えるだけ使うことのみを考えて計算すればよいです。

計算量は \(O(M+K^3)\) です。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAX_A = 310;

int main() {
    ll n;
    int m;
    cin >> n >> m;
    vector<int> mx_b(MAX_A);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        mx_b[a] = max(mx_b[a], b);
    }
    vector<pair<int, int>> ls;
    for (int i = 0; i < MAX_A; i++) {
        if (mx_b[i]) {
            ls.emplace_back(i - mx_b[i], mx_b[i]);
        }
    }
    int sz = MAX_A * (MAX_A + 1) + 10;
    vector<int> dp(sz);
    for (int i = 0; i < dp.size(); i++) {
        for (auto [w, v]: ls) {
            if (i < v or i + w >= dp.size()) continue;
            dp[i + w] = max(dp[i + w], dp[i] + v);
        }
    }
    if (n < dp.size()) {
        cout << n + dp[n] << endl;
        return 0;
    }
    for (int i = 1; i < ls.size(); i++) {
        if (ls[0].second * ls[i].first < ls[0].first * ls[i].second) {
            swap(ls[0], ls[i]);
        }
    }
    auto [w, v] = ls[0];
    ll ans = 0;
    for (int i = MAX_A; i < dp.size(); i++) {
        ll now = dp[i] + (n - i) / w * v;
        ans = max(ans, now);
    }
    cout << n + ans << endl;
}