二维费用背包

题目描述

有 $n$ 件物品，第 $i$ 件物品的重量为 $w_i$，体积为 $c_i$，价值为 $v_i$。你有一个背包，能够承受的总重量上限为 $W$，容纳的总体积上限为 $C$。

每件物品最多选择一次，物品不能拆分。即使两件物品的重量、体积和价值都相同，它们仍然是两件不同的物品，可以分别选择。

请选出若干件物品，使总重量不超过 $W$、总体积不超过 $C$，并使总价值最大。你可以不选任何物品，也不要求恰好用完任何一种容量。

输入格式

第一行包含三个整数 $n,W,C$，分别表示物品数量、重量上限和体积上限。

接下来 $n$ 行，第 $i$ 行包含三个整数 $w_i,c_i,v_i$，分别表示第 $i$ 件物品的重量、体积和价值。

输出格式

输出一个整数，表示满足两种容量限制时的最大总价值。

样例 1

输入

4 5 6
2 4 6
3 2 7
4 3 8
1 2 3

输出

13

说明

选择第 1、2 件物品，总重量为 $2+3=5$，总体积为 $4+2=6$，总价值为 $6+7=13$。

样例 2

输入

4 0 3
0 0 5
0 2 7
1 0 100
0 1 4

输出

16

说明

选择第 1、2、4 件物品，总重量为 $0$，总体积为 $3$，总价值为 $16$。第 3 件物品超过重量上限，不能选择。零重量或零体积物品也只能各选一次。

数据范围

对于所有测试数据，保证：

• $1\le n\le500$。
• $0\le W,C\le200$。
• $0\le w_i,c_i\le200$。
• $0\le v_i\le10^9$。
• 所有输入均为整数。

物品的重量或体积可能超过对应容量上限，也可能同时为 $0$。

答案可能超过 32 位有符号整数的范围，请使用 64 位整数保存总价值。

资源限制

时间限制：2 秒。内存限制：256 MiB。