庆嫦娥一号发射成功
我仰望星空,它是那样寥廓而深邃;那无穷的真理,让我苦苦地求索、追随。——温家宝
嫦娥一号的任务是收集月球资料,关于月亮向来都有很多美好的传说;
相传在远古时期流传一个关于月亮的传说,传说中月亮变成血红色,灾祸就会降临,人间就会陷入般若地狱。远古时候,邪神罗候为了成为天地人三界的统治者,举行了葬月仪式。结果遭到五星阻止,而告失败。贼心不死的罗候立下誓愿,万世之后会完成远古未完的事业!而五星之首的天勇者战尽最后一口气立誓万世之后,五星也会应运而生,阻止罗候葬月。于是一个邪恶的愿望通过轮回的手段得以诞生。
传说中的罗候轮回转世再次于7月1日妄想继续他的葬月仪式。五位勇者--地勇者,水勇者,火勇者,风勇者,空勇者为了阻止邪神罗候挑起了灭世之战。先知曾经说过,月亮之中储存着神奇的能量,分别由被月亮覆盖到的若干1*1的正方形保存着。
为了简化问题,我们将月亮看作一个圆,圆心坐标始终位于原点,只要正方块的任意一个部分在圆之中(仅有交点除外),那么就认为它将赋有月亮中的能量,且每个正方形块所含能量相同,可以认为每个方块中含有一个单位能量,如图红色部分都赋有月亮中的能量(图中月亮共有60个单位能量)。葬月仪式正是通过吸取这些能量来毁灭地球。
我们假设在五星使者来临之前,罗候已经吸取完所有含有月亮中的能量。
但是勇者们为了拯救人类依然不会放弃,五星使者是人世间拥有特殊能力的勇士,他们的法术可以令罗候吸取的能量重新放回到月亮上,但是由于法术有限,他们一共只能施展n次法术,并且在他们施展法术的时候,罗候会趁机偷袭他们,第i次将对他们造成Bi的伤害,勇者们每次施法也可以选择来为:
我仰望星空,它是那样寥廓而深邃;那无穷的真理,让我苦苦地求索、追随。——温家宝
1. 使自己加Ci的血。(每次先加血,后被攻击,且每次加血量不能超过其生命值,超过生命值的部分将忽略不计)
2. 恢复月亮的Ai的能量。(每次先恢复月亮能量,后被攻击,每次恢复月亮能量不能超过月亮的总容量,超过部分将忽略不计,而且如果某次恢复能量后月亮的能量变成了满的,那么罗候就再也没有能量用来攻击了)
当然可以选择不施法,处于防备状态,这样罗候的攻击将对他们无效
五星使者希望借助您的帮助使得月亮恢复尽可能多的能量,他们会将他们的生命值S告诉你以及他们每次法术的效果和他们每次将受到的攻击,如果他们在某一轮牺牲(生命值<=0)。那么接下来将不能继续完成拯救月亮的计划。由于加血奇术属于禁咒,不能连续k轮使用加血术。
如果不能全部恢复月亮能量,五星使者希望您能告诉他们最少月亮还差多少个单位能量不能被恢复,以便制定作战计划(单位:个)。
第一行输入4个正整n, k, R(月亮半径),S(1<=n<=500, 1<=k<=10, 1<=R<=30000, 1<=S<=5000)
2到n+1行每行有3个整数Ai, Bi, Ci (|Ai|<=5000000; |Bi|,|Ci|<=S)
如果他们能成功恢复月亮则输出: We’ll win the game!
否则输出一个整数ans表示最少还差多少个单位能量没被恢复。