题目描述

有 $n$ 种物品要放到一个袋子里，袋子的总容量为 $m$，总载重量为 $r$。第 $i$ 种物品的体积为 $s_i$，把它放进袋子里会获得 $v_i$ 的收益，重量为 $w_i$，每种物品只能取一次。问如何选择物品，使得在物品的总体积不超过 $m$ 并且总重量不超过 $r$ 的情况下，获得最大的收益？请求出最大收益。

输入格式

第一行三个整数 $n,m,r$。

接下来 $n$ 行，每行三个整数 $s_i,v_i,w_i$。

输出格式

一个整数，表示答案。

Samples

5 10 10
3 8 3
4 10 2
5 1 5
1 10 4
4 4 1

28

数据规模

对于所有数据保证 $1≤n,m,r,v_i,w_i,s_i≤100$。