#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,w[1005],c[1005],dp[105],ans=0;
int main(){
	cin>>m>>n;
	for(ll i=1;i<=n;i++)
		cin>>w[i]>>c[i];
	for(ll i=1;i<=n;i++)
		for(ll j=m;j>=w[i];j--)
			dp[j]=max(dp[j],dp[j-w[i]]+c[i]),ans=max(ans,dp[j]);
	cout<<ans<<"\n";
	return 0;
}