1

2

3

4

5

6

7

8

9

#include <iostream>
using namespace std;
int dp[105][1005];

int main() {
	int T, N;
	cin >> T >> N;
	int t[N], v[N];
	for (int i = 1; i <= N; i++)
		cin >> t[i] >> v[i];
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= T; j++) {
			if (t[i] > j)
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + v[i]);
		}
	}
	cout << dp[N][T];
	return 0;
}