解题思路

题意：有若干技能，每次释放造成伤害并消耗固定魔法，且每个技能有冷却时间。角色在存活时间 $T$ 秒内、魔法上限为 $M$，在“魔法耗尽或时间用完之前”尽可能造成最大总伤害。释放无耗时，技能之间互不冲突。

关键观察：

• 因为释放“没有耗时”，且“技能之间互相独立”，同一秒可以同时释放多个不同技能（只要各自冷却好且魔法足够）。

• 因此，唯一的时间相关限制是：在总时长 $T$ 内，每个技能能被使用的次数上限。若技能冷却为 $c$，从第 0 秒开始最早、间隔 $c$ 秒可用，则最多可用

  $$$$

题目内容

小明喜欢玩角色扮演游戏，小明所选角色有若干种攻击技能，每种技能都会对 $BOSS$ 造成不同程度的伤害，同时也会消耗角色一定的魔法值，并且每种技能都有冷却时间(比方说技能 $A$ 的冷却时间是 $30$ 秒,则使用技能 $A$ 后的 $30$ 秒之后才能再次使用)，而且据小明观察角色的血量只能坚持抵抗 $BOSS$ 的攻击若干秒，请你帮助小明找到在角色魔法值耗尽之前或者角色血量耗尽之前能够输出最大伤害的技能组合。

技能总个数不大于 $100$ ，角色魔法值不大于 $1000$ ，角色存活时间不大于 $200$ 秒;技能释放前提是角色所剩魔法值不小于该技能消耗魔法值;血量不会恢复;魔法值不会恢复;技能释放没有耗时;技能之间互相独立。用例会保证输入的格式正确性。

输入描述

第 $1$ 行:技能个数 角色魔法值 角色存活时间

第 $2$ 行:技能 $1$ 造成伤害值 消耗魔法值 冷却时间

…

第 $n+1$ 行:技能 $n$ 造成伤害值 消耗魔法值 冷却时间

如下输入描述:总共有 $3$ 个技能，角色拥有 $100$ 魔法值，可以坚持存活$20$ 秒;第 $1$ 个技能造成伤害 $10$ ，消耗魔法 $8$ ，冷却时间 $5$ 秒;第 $2$ 个技能造成伤害 $5$ ，消耗魔法 $2$ ，冷却时间 $1$ 秒;第 $3$ 个技能造成伤害 $20$ ，消耗魔法 $25$ ，冷却时间 $8$ 秒。

3 100 20

10 8 5

5 2 1

20 25 8

输出描述

输出最大伤害值

样例1

输入

3 100 20
10 8 5
5 2 1
20 25 8

输出

160