#include <iostream>

using namespace std;

const int N = 100010;
int n, m;
int t[N], s[N], dp[N];

int main()
{
    cin >> m >> n;

    for(int i = 1; i <= n; i ++) 
        cin >> s[i] >> t[i];

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(j >= t[i]) dp[j] = max(dp[j], dp[j - t[i]] + s[i]); 
        }
    }

    cout << dp[m] << endl;

}