做法：设 $f(i, j)$ 表示只使用 $1 \sim i$，$j$ 能否取到，取到为 $1$，否则为 $0$。

则

。

在学校 oj 是 45 pts（

//宇宙射线（悲）

#include "bits/stdc++.h"
using namespace std;

int dp[1145][1419];

struct Node {
	int h, a, c;
}f[322620];

bool cmp (Node x, Node y) {
	return x.a < y.a;
}

int n;

int main() {
	scanf ("%d", &n);
	for (int i = 1; i <= n; ++i) scanf ("%d%d%d", &f[i].h, &f[i].a, &f[i].c);
	sort (f + 1, f + n + 1, cmp);
	dp[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= f[i].a; ++j) {
			for (int k = 0; k <= f[i].c; ++k) {
				if ((j - (k * f[i].h)) >= 0) dp[i][j] |= dp[i - 1][j - (k * f[i].h)];
			}
		}
	}
	for (int i = f[n].a; i >= 0; --i) {
		if (dp[n][i] == 1) {
			cout << i;
			return 0;
		}
	}
}