P15116 [ICPC 2024 LAC] Beating the Record

Speedy Greedy 是一名专业的速通玩家：他们反复玩一款电子游戏，目标是尽可能快地通关。 Speedy Greedy 目前挑战的游戏由 $N$ 个关卡组成，按顺序编号为 1 到 $N$。尽管这些关卡必须按顺序完成，但每个关卡在游戏玩法上是相互独立的。也就是说，一个关卡中的任何事件都不会对后续关卡产生相关影响（不像其他游戏那样，物品、法术、分数、生命等会从一个关卡延续到下一个关卡）。 当前游戏最快通关时间的世界纪录是 $T$ 秒。Speedy Greedy 决心打破这个世界纪录，并不在意领先多少。无论是比当前纪录快 1 秒还是快 1000 秒都无关紧要：对 Speedy Greedy 来说，重要的是刷新世界纪录。 速通玩家在游戏中经常根据各种因素（例如角色在游戏中的状况）动态选择和调整行动。重启游戏也很常见，因为一旦超过 $T$ 秒，就没有希望打破世界纪录了。游戏中的任何一次流程都可以在任何时候重启。当速通玩家发出重启指令时，游戏会立即从头开始。因此，为了打破世界纪录，Speedy Greedy 必须在一个单独的流程中按顺序完成 $N$ 个关卡，且总时间少于 $T$ 秒。 Speedy Greedy 如何才能做到这一点呢？好吧，对于这样一位技术高超的速通玩家来说，游戏的大部分部分是完全安全且容易操作的。这些部分花费固定的时间，并且没有失败的风险。然而，在 $N$ 个关卡的每一个中，都有一个非常困难的部分，其游玩结果并不完全受 Speedy Greedy 控制，还取决于所选择的策略。 在每个关卡中，有两种可能的策略，当到达困难部分时，Speedy Greedy 可以恰好选择其中一种进行尝试。每种策略都有自己的成功概率，而关卡实际完成所需的时间取决于所选策略以及尝试是否成功。 为了本问题的目的，我们假设 Speedy Greedy 可以在到达关卡的困难部分的瞬间立即检测到所选的策略是成功还是失败。也就是说，到达关卡的困难部分、选择策略以及得知尝试的策略成功或失败，都是同时发生的事件，发生在完全相同的时刻。 在这种高水平的速通竞赛中，一遍又一遍地反复玩游戏会变得令人疲惫和筋疲力尽。于是 Speedy Greedy 决定以最小化直到打破世界纪录的预期总游戏时间来游玩。你的任务是计算这个最小值。 请注意，总游戏时间不仅包括最终那次耗时少于 $T$ 秒的成功流程（打破世界纪录）的时间，还包括之前所有失败流程所花费的时间。

第一行包含三个整数 $N$（$1 \le N \le 4$）、$T$（$1 \le T \le 5000$）和 $S$（$1 \le S \le 1000$），分别表示关卡数量、当前世界纪录的时间，以及从关卡 1 开始到关卡 1 的困难部分被到达的时刻所经过的时间。 接下来的 $N$ 行中的第 $i$ 行通过六个整数 $P_1, G_1, B_1, P_2, G_2$ 和 $B_2$（对于 $j = 1, 2$，有 $1 \le P_j \le 99$ 和 $0 \le G_j \le B_j \le 1000$）描述了第 $i$ 关的两种策略。 - $P_j$ 表示使用策略 $j$ 时成功的概率（以百分比计）。 - $G_j$ 表示策略 $j$ 的“好时间”，即从策略成功的时刻到下一个关卡的困难部分被到达的时刻所经过的时间。对于最后一个关卡，$G_j$ 表示从策略成功的时刻到游戏完成所经过的时间。 - $B_j$ 表示策略 $j$ 的“坏时间”。它与 $G_j$ 类似，但对应于策略失败情况下的时间。 所有输入时间均以秒为单位。保证输入数据使得打破世界纪录是可能的。

输出一行，表示 Speedy Greedy 打破世界纪录前的最小预期总游戏时间。输出的绝对误差或相对误差不得超过 $10^{-9}$。