#732. 打怪兽

内存限制:512 MiB 时间限制:1000 ms 输入文件:fight.in 输出文件:fight.out
题目类型:传统 评测方式:文本比较
上传者: Payphone_X

题目描述

某人发现了一款新游戏。

游戏中总共有 n 只怪兽,玩家有 m 点体力和 k 点血量。

杀死每个怪兽都需要失去相应的体力和血量(玩家体力或血量为 0 时仍为存活状态),同时获得相应的分数。

请你帮忙计算一下他能拿到的最大分数。

输入格式

第一行三个数字 n 代表怪兽数, m 代表玩家体力, k 代表玩家血量。

下面 n 行,每行三个数字 a_i , b_i , c_i ,分别代表杀死第 i 个怪兽所需的体力、血量以及能得到的分数。

输出格式

仅有一行,包括一个数,代表能够得到的最高分数。

样例

样例输入

7 15 20
1 5 1
3 2 2 
7 5 3
6 2 5
5 1 4
4 3 6
2 7 1

样例输出

15

样例解释

击败第 4 , 5 , 6 只怪兽是最优解

数据范围与提示

对于 30\% 的数据,保证 0 \leq n \leq 10

对于 20\% 的数据,保证 b_i=0,0 \leq n \leq 200

对于 100\% 的数据, 0 \leq n , m , k \leq 200,0 \leq c_i \leq 10^9