#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e+4 + 5;
int t, m;
vector<vector<int> > f;
int at[maxn], av[maxn];
int main()
{
//	freopen("P1616_1.in", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> at[i] >> av[i];
	}
	f.resize(m + 5);
	for (int i = 0; i <= m + 5; i++)
	{
		f[i].resize(t + 5);
	}
	f[0][0] = 0;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= t; j++)
		{
			if (j >= at[i])
			{
				f[i][j] = max(f[i - 1][j], f[i][j - at[i]] + av[i]);
			}
			else
			{
				f[i][j] = f[i - 1][j];
			}
		}
	}
	cout << f[m][t] << endl;
	return 0;
}

在输出答案之后return 3221226356了（答案是正确的）