您正在尝试刷新您最喜爱的视频游戏的记录。游戏由 N 个关卡组成,必须按顺序完成这些关卡才能通关。您通常会尽快完成每个级别,但有时会较慢地完成一个级别。具体来说,您将在 Fi 秒或 Si 秒内完成第 i 个关卡,其中 Fi < Si,并且有 Pi 百分比的机会在 Fi 秒内完成它。完成一个级别后,您可以决定继续游戏并玩下一个级别,或者重置游戏并从第一个级别重新开始。决定和行动都是即时的。
您的目标是在最多 R 秒内按顺序完成所有级别。在实现该目标之前,您希望尽量减少预期的游戏时间。如果您继续并以最佳方式重置,您预计会花多少总时间玩游戏?
输入
输入的第一行包含整数 N 和 R $$( 1 \leq N \leq 5 0, \sum F _ { i } \leq R \leq \sum S _ { i } )$$,分别是你想要完成游戏的关卡数和秒数。接下来是 N 行。第 i 行包含整数 Fi、Si、Pi (1 ≤ Fi < Si ≤ 100, 80 ≤ Pi ≤ 99)、级别 i 的快速时间、级别 i 的慢速时间以及以快速时间完成级别 i 的概率(以百分比表示)。
输出
打印预计总时间。您的答案必须正确,绝对误差或相对误差在 10 - 9 之间。
正式来说,让您的答案为 a,陪审团的答案为 b。如果 $${ \frac { | 则您的答案将被认为是正确的a - b | } { \operatorname* { m a x } ( 1, | b | ) } } \leq 1 0 ^ { - 9 }$$。
示例
输入 #1
1 8 2 8 81
输出 #1
3.14
输入 #2
2 30 20 30 80 3 9 85
输出 #2
31.4
输入 #3
4 319 63 79 89 79 97 91 75 87 88 75 90 83
输出 #3
314.159265358
注意
在第一个示例中,您永远不需要重置。有 81% 的机会在 2 秒内完成关卡,有 19% 的机会需要 8 秒,两者都在目标时间内。预计时间为 0.81·2 + 0.19·8 = 3.14。
在第二个示例中,如果您缓慢完成第一级,则应该在第一级之后重置。平均而言,在第一次快速尝试之前需要 0.25 次慢速尝试。那么无论你完成第二关是快还是慢都没关系。预计时间为 0.25·30 + 20 + 0.85·3 + 0.15·9 = 31.4。