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$ ($1 \le P_j \le 99$ 且 $0 \le G_j \le B_j \le 1000$，其中 $j = 1, 2$)。

$P_j$ 表示使用策略 $j$ 时的成功概率（以百分比表示）。

$G_j$ 表示策略 $j$ 的“好时间”，即从策略成功的那一刻起，到到达下一关困难部分瞬间的时间。对于最后一关，$G_j$ 表示从策略成功的那一刻起，到游戏结束的时间。

最后，$B_j$ 表示策略 $j$ 的“坏时间”。它与 $G_j$ 类似，但表示策略失败时对应的时间。

所有输入的时间均以秒为单位。保证输入数据使得打破世界纪录是可能的。

输出格式

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

样例

样例输入 1

1 100 50
50 48 49 1 1 50

样例输出 1

98.500000000000000

样例输入 2

1 100 50
50 48 49 52 1 50

样例输出 2

97.153846153846154