代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef long long l;
l dp[10000005], a[1005], t[1005], n, m;

int main() {
    scanf("%lld%lld", &n, &m);
    for (l i = 1; i <= m; ++i) {
        scanf("%lld%lld", &t[i], &a[i]);
    }
    for (l i = 1; i <= m; ++i) {
        for (l j = 1; j <= n; ++j) {
            if (j >= t[i]) dp[j] = max(dp[j], dp[j - t[i]] + a[i]);
        }
    }
    printf("%lld", dp[n]);
    return 0;
}