洛谷P1048

#include<iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t, n;
	cin >> t >> n;
	int v[n + 1]; //价值
	int w[n + 1]; //时间
	int f[101][1001];

	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

	for (int i = 1; i <= n; i++)
		for (int j = t; j >= 0; j--) {
			if (j < w[i])
				f[i][j] = f[i - 1][j]; //抄上一个（装不进去）
			else if ( f[i - 1][j] > f[i - 1][j - w[i]] + v[i] )
				f[i][j] = f[i - 1][j]; //抄上一个（装进去费空间）
			else
				f[i][j] = f[i - 1][j - w[i]] + v[i]; //装进去！
		}

	cout << f[n][t];
	return 0;
}