补题链接：Here
首先必须理解到这是一道背包问题，但直接写背包肯定是错的，因为这里多了一个时间的限制：物品价值随时间变化
同样是背包但是先进背包和后进背包有区别
因此需要考虑贪心策略下背包
对于两个物体 (A,B) 先取 (A) 物体比先取(B) 物体优
数学表达
[a_i- b_i * c_i + a_j - b_j * (c_i + c_j) > a_j - b_j * c_j + a_i - b_i*(c_i+c_j) \
化简: b_j* c_i < b_i * c_j
]
排序后进行背包就行了
注意题目要求必须至少做一道菜, 这里有个人尽皆知的小技巧：把 dp 数组初始化为无穷小，且 (dp_0 = 0) 这样保证至少取一个
using ll = long long;
const int N = 1 << 20;
ll dp[N];
ll a[N], b[N], c[N], j[N], k[N];
bool cmp(int x, int y) { return b[j[x]] * c[y] > b[j[y]] * c[x]; }
void solve() {
int n, m, t;
cin >> n >> m >> t;
for (int i = 1; i <= n; ++i) cin >> b[i];
for (int i = 1; i <= m; ++i) cin >> j[i] >> a[i] >> c[i], k[i] = i;
sort(k + 1, k + 1 + m, cmp);
memset(dp, -0x3f, sizeof(dp));
for (int i = 1; i <= m; ++i) {
int v = k[i];
for (int l = t; l >= c[v]; --l)
dp[l] = max(dp[l], dp[l - c[v]] + a[v] - l * b[j[v]]);
}
ll ans = -1e18;
for (int i = 1; i <= t; ++i) ans = max(ans, dp[i]);
cout << ans << "
";
}