#include <bits/stdc++.h>

using namespace std;
const int N = 1100;
int f[N], v[N], w[N];
// 视频讲解
// https://www.bilibili.com/video/BV1u7411t7E5
/**
 需要理解的是，二维降为一维，为什么要用倒序
 */
int main() {
    //输入+输出重定向
    freopen("../1299.txt", "r", stdin);

    int n, m;
    cin >> m >> n;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) { //如果继续正序，会先算小的，与原来的概念就不一样了，只有从后向前算，依赖的才没有改变
            if (v[i] <= j) f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    //关闭文件
    fclose(stdin);
    return 0;
}