P12067 [THOI 2013] 魔塔

搬运自 [2013 年清华大学信息学邀请赛](https://gitlink.org.cn/thusaa/thoi2013)。

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

输入的第一行包含三个正整数 $n,C_A,C_D$，分别表示怪物数量、购买单位攻击力的价格以及购买单位防御力的价格。 接下来 $n$ 行描述怪物的属性，其中第 $i$ 行包含三个正整数 $H_i,A_i,D_i$，表示第只怪物的生命值、攻击力和防御力。

输出为一行，包含三个正整数，表示勇士的生命值、攻击力和防御力，如果有多种方案均能战胜所有怪物且花费金币数最少，输出任意一种即可。注意：尽管防御力为零可能更优，但本题要求输出的防御力必须**大于零**。

### 【对样例的说明】 - 首先，与第一只怪物战斗，经过 $1$ 秒钟勇士损失 $25$ 点生命值并取得胜利； - 然后，与第二只怪物战斗，经过 $3$ 秒钟勇士损失 $15$ 点生命值并取得胜利； - 最后，与第三只怪物战斗，经过 $12$ 秒钟勇士取得胜利且未损失生命值； - 最终，勇士消灭了所有怪物，剩余 $1$ 点血量，共花费 $41+2\times10+5\times5=86$ 枚金币。 ### 【数据规模与约定】 - $10\%$ 的测试数据满足 $n\le50$，$H_i,A_i,D_i\le1000$。 - $40\%$ 的测试数据满足 $n\le1000$，$H_i,A_i,D_i\le10^5$。 - $70\%$ 的测试数据满足 $n\le2500$，$H_i,A_i,D_i\le5\times10^5$。 - 所有的测试数据满足 $n\le5000$，$H_i,A_i,D_i\le10^6$，$C_A,C_D\le10^6$。