题目描述

给定 $n$ 个物品，每个物品有重量 $w_i$、体积 $v_i$、价值 $val_i$，每个物品至多选一次。 背包有承重上限 $W$ 和容积上限 $V$，求不超出限制时能获得的最大总价值。

输入格式

第一行三个整数 $n, W, V$。 接下来 $n$ 行，每行三个整数 $w_i, v_i, val_i$。

输出格式

一行一个整数，表示最大总价值。

样例输入

3 5 5
2 3 4
3 2 5
4 4 7

样例输出

9

数据范围与提示

• 对于 $100\%$ 的数据： $1 \le n \le 1000$，$1 \le W,V \le 500$ $1 \le w_i \le W$，$1 \le v_i \le V$，$1 \le val_i \le 10^6$