#include<bits/stdc++.h>
using namespace std;
int w[10001], c[10001];
int f[10001];
int main()
{
	int t, m;
	cin >> t >> m;
	for(int i = 1; i <= m; i ++)
		cin >> w[i] >> c[i];
	for(int i = 1; i <= m; i ++)
		for(int v = w[i]; v <= t; v ++)
			if(f[v - w[i]] + c[i] > f[v])
				f[v] = f[v - w[i]] + c[i];
	cout << f[t];
	return 0;
}