You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小A 在玩一款好玩的冒险游戏。

在这个游戏中，小A有 $H$ 的生命值和 $K$ 体力值。

在一天中，游戏系统会发布 $n$ 个怪物讨伐任务。 完成第 $i$ 个任务会消耗小A $h_i$ 的生命值和 $k_i$ 的体力值，然后获得 $w_i$金币。

当小A 的生命值或体力值下降到小于 $0$ 时，她就会死亡。 但当他可以扣除生命值来补充能量值。形式化来说，在任意时刻，他可以选择一个整数 $a$，使自己的生命值 $-a$ ，让体力值 $+a$ 。

现在在保证小A不会死亡的情况下，他最多能获得多少金币。

输入格式

第一行三个整数 $n,H,K$ 。

接下来 $n$ 行，每行三个整数 $h_i,k_i,w_i$，含义如题。

输出格式

共一行一个整数，表示答案。

5 10 10
7 2 8
5 1 2
3 5 7
2 4 9
0 5 4

21

样例解释

小A先消耗一点生命值，转化为一点体力值，选择第 $1,4,5$ 个任务，需要 $7+3=9$ 生命值，$2+4+5=11$ 体力值，获得 $8+9+4=21$ 个金币。

数据范围

对于所有数据 $n\le 1000,0\le H,K,j_i,k_i\le 300,w_i\le 10^9$ 。