#include <iostream>
#include <cstring>
using namespace std;
long long f[10000005],n,m;
int v[10005],w[10005];
int dp(int amount){
	if(f[amount] >= 0) return f[amount];
	int res = 0;
	for(int i = 1;i <= n;i++){
		if(amount - w[i] < 0) continue;
		res = max(res,dp(amount - w[i]) + v[i]);
	}
	return f[amount] = res;
}
int main(){
	memset(f,-1,sizeof f);
	cin >> m >> n;
	for(int i = 1;i <= n;i++)
		cin >> w[i] >> v[i];
	cout << dp(m);
	return 0;
}