题目描述

一场篮球比赛还剩 time 秒，A、B 两队轮流持球进攻。忽略三分球和犯规，每次投篮命中得到 $2$ 分。两队都没有暂停，因此不能主动停止比赛计时。

一次进攻中，持球队在投篮前要进行若干秒的组织。设数组长度为 $n$。若一支球队组织了 $i+2$ 秒（$0\le i<n$）后投篮，则该次投篮命中概率由对应的 percentage 数组给出；若投篮未命中，则以对应的 rebound 概率抢到前场篮板并继续持球，否则球权交给另一队。抢到前场篮板后，下一次投篮的组织时间重新计算。

由于进攻时间限制，每次持球后必须在数组允许的某个组织时间后投篮，且不能在组织不足 $2$ 秒时投篮。

现在 A 队刚刚获得球权。A 队会选择策略使自己最终获胜的概率最大，而 B 队会选择策略使 A 队获胜的概率最小。比赛结束时平局不算 A 获胜。

求在双方都采用最优策略时，A 队最终获胜的概率。

输入格式

第一行输入四个整数 $n, time, scoreA, scoreB$，分别表示数组长度、剩余时间以及两队当前得分。

接下来 $n$ 行，第 $i$ 行输入四个整数 percentageA[i]、percentageB[i]、reboundA[i]、reboundB[i]（下标从 $0$ 开始），分别表示当组织时间为 $i+2$ 秒时：

• A 队投篮命中百分比；
• B 队投篮命中百分比；
• A 队投失后抢到前场篮板的百分比；
• B 队投失后抢到前场篮板的百分比。

输出格式

输出一个实数，表示双方最优策略下 A 队最终获胜的概率。

答案的绝对误差或相对误差不超过 $10^{-9}$。

样例 1

输入

4 5 99 100
10 10 1 1
20 20 2 2
30 30 3 3
40 40 4 4

输出

0.4

解释

A 队只落后 $1$ 分，最优做法是组织满 $5$ 秒后在比赛结束前投篮，此时命中概率为 $40\%$。

样例 2

输入

4 5 98 100
10 10 1 1
20 20 2 2
30 30 3 3
40 40 4 4

输出

0.0

解释

即使 A 队命中，也只能追平，因此无法获胜。

样例 3

输入

4 10 98 100
10 10 1 1
20 20 2 2
30 30 3 3
40 40 4 4

输出

0.011519999999999997

数据范围

• $1\le n\le 50$；
• percentageA、percentageB、reboundA、reboundB 中每个数均在 $[0,100]$ 内；
• $0\le scoreA,scoreB\le100$；
• $1\le time\le300$；
• 时间按整数秒离散处理。