题目描述

给定 $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$