#include<bits/stdc++.h>
using namespace std;
int t, m, s[105], w[105];
int fs[105][1005];
int dfs(int x, int num) {
    int res=0;
    if (fs[x][num])
        return fs[x][num];
    if (x > m)
        return 0;
    else{
        if(s[x] > num)
            res = 0;
        else if (s[x] <= num)
            res = max(dfs(x + 1, num), dfs(x + 1, num - s[x]) + w[x]);
    }
    return fs[x][num]=res;
}
int main() {
    cin >> t >> m;
    for (int i = 1; i <= m; i++)
        cin >> s[i] >> w[i];
    int ans = dfs(1, t);
    cout << ans;
    return 0;
}