#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,m,w[1005],v[1005];
int dp[1005][1005];
signed main(){
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>w[i]>>v[i];
	}
	memset(dp,-1,sizeof(dp));
	dp[0][0]=0;//初始状态
	for(int i=1;i<=m;i++){
		for(int j=0;j<=t;i++){
			if((j-w[i])>=0 && dp[i-1][j-w[i]]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
			else dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[m][t];
	return 0;
}

re