[Thu Summer Camp 2013]魔塔

时间限制:10s      空间限制:128MB

题目描述

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

勇士在魔塔内行走,消灭怪物,积累宝物,最终解救出困在塔顶的公主。 
勇士的能力通过生命值、攻击力和防御力三个属性值来表示 (均为正整数) ,
怪物的能力表示与勇士相同。勇士在和一个怪物战斗时,双方会面对面站好,然
后每秒钟攻击对方一次。当勇士攻击力大于怪物防御力时,怪物将被扣除勇士攻
击力减去怪物防御力的血量,否则怪物不扣血。同时,当怪物攻击力大于勇士防
御力时,勇士将被扣除怪物攻击力减去勇士防御力的血量,否则勇士不扣血。若
经过若干秒的攻击后,有至少一方的血量小于等于零,则此次战斗结束。注意,
由于双方同时攻击,所以可能会出现战斗结束时双方血量均小于等于零的情况。
当且仅当战斗在有限回合内结束且勇士的剩余血量大于零时,勇士获得胜利。例
如:下图勇士与怪物的战斗中,每秒钟勇士的攻击使怪物扣除 9点血量,怪物的
攻击使勇士扣除 10 点血量,6 秒钟后怪物的血量低于零,勇士剩余 940 点生命
值并取得胜利。  
沫沫喜欢上魔塔的主要原因是,她不需要用精妙的操作来打败怪物。相反,
一旦勇士的属性确定,勇士与每只怪物的战斗结果就已经确定。游戏中,勇士必
须击败N只怪物才能救出公主, 沫沫需要决定勇士的初始属性与消灭怪物的顺序。  
在踏入魔塔之前,沫沫可以用金币为勇士购买初始属性,每一点生命值需要
1枚金币,每一点攻击力需要Ca枚金币,每一点防御力需要Cd枚金币。沫沫想通
过选择合理的消灭怪物的顺序,以减少金币的花费, 并让勇士战胜所有N只怪物,
成功救出公主。现在请你来计算最少需要多少金币才能完成该任务。 


输入格式

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

力的价格以及购买单位防御力的价格。 
接下来N行描述怪物的属性,其中第i行包含三个正整数Hi,Ai,Di表示第i只
怪物的生命值、攻击力和防御力。 


输出格式

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

有多种方案均能战胜所有怪物且花费金币数最少,输出任意一种即可。注意:尽
管防御力为零可能更优,但本题要求输出的防御力必须大于零。 


样例输入

3 2 5 
5 30 5 
20 10 3 
100 5 1 

样例输出

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。
 


题目来源

没有写明来源