#include<bits/stdc++.h>
using namespace std;
int t, n, m;
unordered_map<int, unordered_map<int, int>> s;
vector<pair<int, int>> v(1);
int dfs(int now, int time){
	if(s[now][time])
		return s[now][time];
	if(now > n)
		return 0;
	else if(time >= v[now].first)
		return s[now][time] = max(dfs(now + 1, time - v[now].first) + v[now].second, dfs(now + 1, time));
	else
		return 0;
}signed main(){
	scanf("%d%d", &t, &n);
    m = n;
	for(int i = 1; i <= m; ++i){
		pair<int, int> p;
		scanf("%d%d", &p.first, &p.second);
		int k = t / p.first;
		n += k;
		v.resize(v.size() + k, p);
	}sort(v.begin(), v.end());
	printf("%d", dfs(1, t));
	return 0;
}