#include<bits/stdc++.h>

using namespace std;

const int maxn=10005;

int dp[maxn][maxn],w[maxn],v[maxn],n,m;

int main(){

cin>>m>>n;

for(int i=1;i<=n;i++) cin>>w[i]>>v[i];

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

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

}

cout<<"max="<<dp[n][m];

return 0;

}