#include<iostream>
#include<cmath>
#include<map>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
int f[10000000];
int n,m;
int v[10000000],w[10000000];
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=w[i];j<=m;j++){
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++)ans=max(ans,f[i]);
	cout <<ans;
	return 0;
}