#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4*3+100; 
long long n,c,w[maxn],v[maxn],dp[maxn];
int main(){
	freopen("delicious.in","r",stdin);
	freopen("delicious.out","w",stdout);
	cin>>c>>n;
	for(long long i=1;i<=n;i++){
		scanf("%d%d",&w[i],&v[i]);
		for(long long j=c;j>=w[i];j--){
			dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
		}
	}
	cout<<dp[c];
	fclose(stdin);
	fclose(stdout);
	return 0;
}