#include<bits/stdc++.h>

using namespace std;

const int maxn=10005;

int dp[maxn][maxn];

int k[maxn],y[maxn];

int main(){

int n,m;

cin>>m>>n;

for(int i=1;i<=n;i++) cin>>k[i]>>y[i];

for(int i=1;i<=n;i++){

	for(int j=1;j<=m;j++){
  
		if(k[i]>j){
    
			dp[i][j]=dp[i-1][j];
      
		} else {
  
			dp[i][j]=max(dp[i-1][j],y[i]+dp[i-1][j-k[i]]);
    
		}
  
	}

}

cout<<dp[n][m];

return 0;

}