T4 双重背包（knap）

题目描述

小明有一个背包，它同时受到两种资源的限制：背包的体积上限为 $V$，承重上限为 $W$。

现在有 $n$ 件物品，第 $i$ 件物品的体积为 $a_i$、重量为 $b_i$、价值为 $c_i$。每件物品只能选择放入或不放入背包。请你帮小明选出若干物品放入背包，使得它们的总体积不超过 $V$、总重量不超过 $W$，并让总价值最大。

输入文件 knap.in，输出文件 knap.out。

输入格式

输入第一行包含三个正整数 $n,V,W$，分别表示物品数量、体积上限与承重上限。

接下来 $n$ 行，每行三个整数 $a_i,b_i,c_i$，依次表示第 $i$ 件物品的体积、重量与价值。

输出格式

输出共一行，包含一个整数，表示能获得的最大总价值。

样例 1 输入

3 5 5
2 1 3
3 2 4
1 4 2

样例 1 输出

7

样例 1 解释

选择第 $1$ 件和第 $2$ 件物品：总体积 $2+3=5\le 5$，总重量 $1+2=3\le 5$，总价值 $3+4=7$，为最优方案。

若再加入第 $3$ 件物品，总体积为 $6>5$，不可行。

样例 2 输入

8 20 20
9 4 41
9 5 6
6 4 18
9 7 45
7 9 59
4 3 62
5 7 1
3 4 78

样例 2 输出

217

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n\le 20$。
• 对于另 $30\%$ 的数据，保证 $n\le 50$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 100$，$0\le a_i\le V\le 100$，$0\le b_i\le W\le 100$，$1\le c_i\le 100$。