#include<bits/stdc++.h>

using namespace std;

/*
知识点内容：动态规则0-1背包问题

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

using namespace std;
int w[105], val[105];
int dp[105][1005];

int main() {
    int t, m;
    cin >> t >> m;
    for (int i = 1; i <= m; i++)
        cin >> w[i] >> val[i];

    for (int i = 1; i <= m; i++) //物品
        for (int j = t; j >= 0; j--) //容量
        {
            if (j >= w[i])
                dp[i][j] = max(dp[i - 1][j - w[i]] + val[i], dp[i - 1][j]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    cout << dp[m][t] << endl;
    return 0;
}