U459499 提瓦特的日常 · 其一

~~交模板就能过的大水题~~ [系列题单指路](/training/570608) ### 提瓦特的日常 · 蛋糕采购 扮演水神的工作结束后，芙宁娜来到枫丹庭的一家蛋糕店购买蛋糕。尽管她很想将这里所有种类的蛋糕都购买一份，但碍于背包容量和财力不足，她只能选择一部分。芙宁娜希望你能帮她选出最喜欢的蛋糕种类。

蛋糕店里一共有 $n$ 种蛋糕，由于芙宁娜不希望买到的蛋糕口味太重复，所以她**每种最多只会买一块**。 每种蛋糕都有一定的价格且占有一定的空间，第 $i$ 种蛋糕的价格是 $C_i$ 摩拉，占背包空间为 $V_i$，芙宁娜对这种蛋糕的喜爱程度为 $L_i$。芙宁娜带有 $c$ 枚摩拉，她的背包容量为 $v$。 请写一个程序，帮助芙宁娜选择一种采购蛋糕的方案，使得采购的蛋糕总价格不超过芙宁娜携带的金额，所占背包空间不超过芙宁娜的背包容量，且芙宁娜对这些蛋糕的喜爱程度总和最大。输出这个最大的总和。

第一行包含三个整数：$n,v,c$，分别表示蛋糕的数量、芙宁娜的背包容量、芙宁娜携带的金额。 之后 $n$ 行，每行三个整数 $V_i,C_i,L_i$ ，分别表示每种蛋糕占的空间、购买它需支付的价格、芙宁娜对它的喜爱程度。

一个整数，即最大喜爱程度总和。

对于 $100\%$ 的数据，$n,v,c \leq 150,V_i,C_i\leq50,L_i\leq500$。