[Thu Summer Camp 2013]魔塔

内存限制：128 MiB 时间限制：10 Sec

沫沫最近迷上了一款名叫魔塔的角色扮演类游戏。在游戏中，玩家需要控制

勇士在魔塔内行走，消灭怪物，积累宝物，最终解救出困在塔顶的公主。

勇士的能力通过生命值、攻击力和防御力三个属性值来表示（均为正整数），

怪物的能力表示与勇士相同。勇士在和一个怪物战斗时，双方会面对面站好，然

后每秒钟攻击对方一次。当勇士攻击力大于怪物防御力时，怪物将被扣除勇士攻

击力减去怪物防御力的血量，否则怪物不扣血。同时，当怪物攻击力大于勇士防

御力时，勇士将被扣除怪物攻击力减去勇士防御力的血量，否则勇士不扣血。若

经过若干秒的攻击后，有至少一方的血量小于等于零，则此次战斗结束。注意，

由于双方同时攻击，所以可能会出现战斗结束时双方血量均小于等于零的情况。

当且仅当战斗在有限回合内结束且勇士的剩余血量大于零时，勇士获得胜利。例

如：下图勇士与怪物的战斗中，每秒钟勇士的攻击使怪物扣除 9点血量，怪物的

攻击使勇士扣除 10 点血量，6 秒钟后怪物的血量低于零，勇士剩余 940 点生命

值并取得胜利。

沫沫喜欢上魔塔的主要原因是，她不需要用精妙的操作来打败怪物。相反，

一旦勇士的属性确定，勇士与每只怪物的战斗结果就已经确定。游戏中，勇士必

须击败N只怪物才能救出公主，沫沫需要决定勇士的初始属性与消灭怪物的顺序。

在踏入魔塔之前，沫沫可以用金币为勇士购买初始属性，每一点生命值需要

1枚金币，每一点攻击力需要Ca枚金币，每一点防御力需要Cd枚金币。沫沫想通

过选择合理的消灭怪物的顺序，以减少金币的花费，并让勇士战胜所有N只怪物，

成功救出公主。现在请你来计算最少需要多少金币才能完成该任务。

输入的第一行包含三个正整数N,Ca,Cd，分别表示怪物数量、购买单位攻击

力的价格以及购买单位防御力的价格。

接下来N行描述怪物的属性，其中第i行包含三个正整数Hi,Ai,Di表示第i只

怪物的生命值、攻击力和防御力。

输出为一行，包含三个正整数，表示勇士的生命值、攻击力和防御力，如果

有多种方案均能战胜所有怪物且花费金币数最少，输出任意一种即可。注意：尽

管防御力为零可能更优，但本题要求输出的防御力必须大于零。


			41 10 5

首先，与第一只怪物战斗，经过 1秒钟勇士损失25点生命值并取得胜利；

然后，与第二只怪物战斗，经过 3秒钟勇士损失15点生命值并取得胜利；

最后，与第三只怪物战斗，经过 12秒钟勇士取得胜利且未损失生命值；

最终，勇士消灭了所有怪物，剩余 1点血量，共花费41 + 2 × 10 + 5 × 5 = 86

枚金币。

所有的测试数据满足N<=5000，Hi,Ai,Di <=10^6，CA, CD <=10^6。

#4141. [Thu Summer Camp 2013]魔塔