#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> v;
int t, n, ans;
void dfs(int tm, int num, int tot){
	if(tm > t)
		return;
	ans = max(ans, tot);
	for(int i = num + 1; i < n; ++i)
		dfs(tm + v[i].first, i, tot + v[i].second);
}signed main(){
	cin >> t >> n;
	for(int i = 0; i < n; ++i){
		pair<int, int> p;
		scanf("%d%d", &p.first, &p.second);
		v.push_back(p);
	}sort(v.begin(), v.end());
	dfs(0, -1, 0);
	cout << ans;
	return 0;
}