#include<iostream>
const long long T = 100000000+1000;
const long long M = 1010;
struct medcial {
	long long cost, val;
}list[M] = {};

long long dp[T] = {};
long long t, m;

long long DP(long long x);

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false);
	cin >> t >> m;
	for (long long i = 1; i <= m; i++)
		cin >> list[i].cost >> list[i].val;
	for (long long i = t; i >= 0; i--)
		dp[i] = DP(i);
	cout << dp[0];
	return 0;
}

long long DP(long long x) {
	long long max = dp[x];
	for (long long i = 1; i <= m; i++) {
		if (list[i].cost + x > t)
			continue;
		if (max < dp[x + list[i].cost] + list[i].val)
			max = dp[x + list[i].cost] + list[i].val;
	}
	return max;
}

因为前面wa干脆改掉了所有int 但还是有四个。。完全找不出错在哪 。。。dalao救命