#include<bits/stdc++.h>

using namespace std;

/*
知识点内容：动态规则完全背包

文档内容参考：
https://www.cnblogs.com/aiguona/p/7274876.html
*/

using namespace std;

int w[300], c[300], f[300010];
int V, n;

int main() {
    scanf("%d%d", &V, &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &c[i]);
    }
    for (int i = 1; i <= n; i++)
        for (int j = w[i]; j <= V; j++)//注意此处，与0-1背包不同，这里为顺序，0-1背包为逆序
            f[j] = max(f[j], f[j - w[i]] + c[i]);
    printf("max=%d\n", f[V]);
    return 0;
}