#include <fstream>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int n,g, w[5004], p[5004];
long dp[2][10004];


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

    for(int i=1; i<=g; ++i){
        cin>>w[i]>>p[i];
    }


    for(int i=w[1]; i<=n; ++i) dp[1][i] = p[1];
    int j=2;
    while(j<=n){
        for(int i=1; i<=g; ++i){
            dp[j%2][i] = max(dp[j%2][i-1],max(dp[(j-1)%2][i],dp[(j-1)%2][i-w[j]]+p[j]));
        }
        ++j;
    }
    cout<<dp[n%2][g];




    return 0;
}