#include<iostream>
using namespace std;
//完全背包问题
struct goods
{
	int value;
	int cost;
};
goods st[10005];

long long dp[10005];

int main() {
	int t = 0;
	int m = 0;
	cin >> t >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> st[i].cost >> st[i].value;
	}

	//一维优化形式，降低时空复杂度
	for (int i = 1; i <= 10004; i++)
		dp[i] = 0;
	for(int i=1;i<=m;i++)
		for (int j = st[i].cost; j<=t;j++)
		{
			dp[j] = max(dp[j], dp[j - st[i].cost] + st[i].value);
		}
	cout << dp[t] << endl;

	return 0;
}