思路

经典的二维费用背包问题。

状态定义：$f[i][j][k]$ 表示前 $i$ 个事件，花费至多 $j$ 的时间和至多 $k$ 的精力，能够获得最大的快乐值。

状态转移：

• 不选择第 $i$ 个事件

  $f[i][j][k] = f[i-1][j][k]$

题目描述

小红有许多生活琐事。已知他生活中有$n$个事件，解决第$i$个事件需要他花费$t_i$的时间和$h_i$的精力，并能获得$a_i$的快乐值。

小红想知道，在总花费时间不超过T且总花费精力不超过H的前提下，小红最多可以获得多少快乐值？

输入格式

第一行输入一个正整数n，代表事件的数量。

第二行输入两个正整数T和H，代表时间限制和精力限制

接下来的n行，每行输入三个正整数$t_i$,$h_i,a_i$,代表分享第i个事件需要花费t;的时间、$h_i$的精力，收获$a_i$的快乐值

$1 \leq n \leq 50$

$1 \leq T,H \leq 500$

$1 \leq t, h_i \leq 30$

$1 \leq a_i \leq 10^9$

输出格式

一个整数，代表小红最多的快乐值。

4
10 15
1 7 5
5 4 6
3 8 1
10 5 7

11