#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int w[N],v[N],f[N][N];
int t,m;
int main()
{
	freopen("medic.in","r",stdin);
	freopen("medic.out","w",stdout);
	cin >> t >> m;
	for(int i = 1;i <= m;i++)
	{
		cin >> w[i] >> v[i];
	}
	memset(f,0,sizeof(f));
	for(int i = 1;i <= m;i++)
	{
		for(int j = 0;j < w[i] && j <= t;j++)
			f[i][j] = f[i - 1][j];
		for(int j = w[i]; j <= t; ++j)
			f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
	}
	cout << f[m][t] << endl;
	return 0;
}