#include <fstream>
#include <algorithm>

using namespace std;

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

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


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

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

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


    return 0;
}