Description

我们现在考虑一个简化的模型。对于一轮比赛，彩民需要竞猜其中 $n$ 场比赛的结果，每场比赛的胜负平都有一个概率 $p(i, r)$ 。其中，$i$ 表示第 $i$ 场比赛。$r\in \{0,1,2\}$，分别表示主队比赛结果的负、平、胜。$p(i, r)$ 则表示第i场比赛、结果为r的概率。此外，还有一个概率 $q(i, r)$，表示第 $i$ 场比赛，投注购买结果为 $r$ 的概率，即总注数中购买该场次某一比赛结果的概率。

例如，如果 $q(1,0) = 0.5$，我们可以知道第一场比赛有 $50\%$ 的投注会买主队输球。我们假设这 $n$ 场比赛互不相关，即 $p(i, r)$ 的结果不会受 $p(j, r’)$ 的影响，$q(i, r)$ 的结果也不会受 $q(j, r’)$ 的影响（$r \ne r’$）。

在这个模型里，我们规定，必须猜中全部 $n$ 场比赛的结果才能获奖。总奖金为 $M$，由所有获奖的投注平分。因此，对于一个单式投注 $R_i = \{r_{i1}, r_{i2}, \ldots ,r_{in}\}$，$r_{ij}$ 表示投注 $R_i$对第j场比赛的预测结果，它的中奖概率为：

$$P(R_i)=\prod\limits_{j=1}^np(j,r_{ij})$$

设投注总数为 $N$，那么中奖的投注总数为：

$$N\cdot Q(R_i)=N\cdot\prod\limits_{j=1}^nq(j,r_{ij})$$

于是，投注 $R_i$ 所能得到的奖金的期望（平均意义下能够获得的奖金数）就是：

$$\dfrac{M}{N\cdot Q(R_i)} \cdot P(R_i)$$

以上考虑的仅仅是单式投注的情况，即仅考虑单注 $R_i$ 的中奖情况。对于复式投注，情况要复杂一些。采用复式投注时，投注的是一个集合 $R = \{R1, R2, …, Rk\}$，其中k是投注的数量。例如，三场比赛，第一场猜“胜负”，第二场猜“平”，第三场猜“负平”，则 $k = 4$，$R$ 集合所包含的四个元素如下如下：

	$r_{i1}$	$r_{i2}$	$r_{i3}$
$R_1$	0	1	0
$R_2$			1
$R_3$	2		0
$R_4$			1

复式投注R中，只要有一个 $Ri$ 猜对所有比赛结果，即可中奖。因此，复式投注R所能获得的奖金的期望就是：

$$\sum_{R_i\in R}\dfrac{M}{N\cdot Q(R_i)} \cdot P(R_i)$$

我们的问题是，给定 $n$ 场比赛的信息（胜负平的概率和彩民购买三种结果的概率），以及复式投注中可以购买的最大注数 $U$，要求设计一种复式投注的方案，在不超过最大注数（复式投注的注数 $k \le U$）的前提下，使得获得奖金的期望最大。

Input Format

第一行四个正整数 $n, N, M, U$，其中 $n, U \le 10^4, N, M \le 10^9$。

以下 $n$ 行，每行六个实数。第 $i + 1$ 行的六个实数为 $p(i, 0), p(i, 1), p(i, 2), q(i, 0),q(i, 1),q(i, 2)$，用来描述第 $i$ 场比赛的相关信息。其中，$p(i, 0) + p(i, 1) + p(i, 2) = 1$,，$q(i, 0) + q(i, 1) + q(i, 2) = 1$，$q(i, j) ≠ 0$。

Output Format

一个实数，表示最大的奖金期望的自然对数。

$$\ln \left( \operatorname{max}_{\lvert R \rvert \le U}\left\{\sum_{R_i\in R}\dfrac{M}{N\cdot Q(R_i)} \cdot P(R_i)\right\}\right)$$

输出保留 $3$ 位小数（四舍五入）。

1 10 10 1
0.3 0.2 0.5 0.7 0.2 0.1

1.609