#include<iostream>
using namespace std;
int n,w,a[5005],v[5005],dp[2][5005];
int main(){
	cin>>w>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>v[i];
	int cur=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=w;j++){
			if(j<a[i]) dp[cur][j]=dp[cur^1][j];
			else dp[cur][j]=max(dp[cur^1][j],dp[cur^1][j-a[i]]+v[i]);
		}
		cur^=1;
	}
	cout<<dp[cur^1][w]<<"\n";
	return 0;
}