#include <bits/stdc++.h>
using namespace std;
int c[1000000] , w[1000000];
int dp[1000][1000];
int main(){
    int m , n;
    cin >> m >> n;
    for (int i=1;i<=n;++i) cin >> c[i] >> w[i];
    for (int i=1;i<=n;++i){
        for (int j=0;j<=m;++j){
            if (j>=c[i]) dp[i][j] = max(dp[i-1][j] , dp[i-1][j-c[i]]+w[i]);
            else dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}