题目描述

南非世界杯离我们越来越近了，与足球有紧密联系的足球彩票也越来越引起了人们的强烈关注。

了解足球彩票的人可能知道，足球彩票中有一种游戏叫做“胜负彩”，意为猜比赛的胜负。下面是一些与胜负彩有关的术语：
注：每一组有效组合数据。
投注：彩民以现金购买足球彩票的行为。
单式投注：彩民对于所有球队的比赛成绩均只选择一种预测结果的投注方式。投注的数量（注数）为1。
复式投注：彩民对于某些场次的比赛成绩选择两种以上的预测结果的投注方式。投注的数量为复式投注的组合数。例如，某彩民对一场比赛预测了两个结果（例如，胜平），另一场比赛预测了三个结果（胜负平），其他比赛都只预测了一种结果，那么注数就是 $2 \times 3 = 6$。这样的一个复式投注，可以看成一个包含六种单式投注的集合。

胜负彩的玩法一般是这样的。彩票机构指定一轮比赛中的若干场，让彩民去猜每场比赛的结果（胜、负、平）。根据彩民猜中比赛的场次，来确定中奖的额度。

我们现在考虑一个简化的模型。对于一轮比赛，彩民需要竞猜其中 $n$ 场比赛的结果，每场比赛的胜负平都有一个概率 $p(i,r)$ 。其中， $i$ 表示第 $i$ 场比赛。 $r = 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\not = r'$）。

在这个模型里，我们规定，必须猜中全部 $n$ 场比赛的结果才能获奖。

总奖金为 $m$ ，由所有获奖的投注平分。因此，对于一个单式投注 $R_i=\{r_{i,1}, r_{i,2}, …, r_{i,n}\}$，$r_{i,j}$ 表示投注 $R_i$ 对第 $j$ 场比赛的预测结果，它的中奖概率为：

$$P(R_1)=\prod_{j=1}^np(j,r_{i,j})$$

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

$$\sum_{R_i\in R}\frac{m}{N\times Q(R_i)}\times P(R_i) $$

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

$$\frac{m}{N\times Q(R_i)}\times P(R_i)$$

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

$$R_1=(r_{1,1}=0,r_{1,2}=1,r_{1,3}=0)\\ R_2=(r_{2,1}=0,r_{2,2}=1,r_{2,3}=1)\\ R_3=(r_{3,1}=2,r_{3,2}=1,r_{3,3}=0)\\ R_4=(r_{4,1}=2,r_{4,2}=1,r_{4,3}=1) $$

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

$$N\times Q(R_i)=N\times \prod_{j=1}^n q(j,r_{i,j})$$

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

输入格式

第一行四个整数 $n, N, m, U$。
以下 $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) \not = 0$。

输出格式

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

$$\ln \bigg(\max_{|R|\leq U}\bigg\{\sum_{R_i\in R}\frac{m}{N\times Q(R_i)}\times P(R_i)\bigg\}\bigg) $$

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

1 10 10 1
0.3 0.2 0.5 0.7 0.2 0.1

1.609

数据规模与约定

对于 $100\%$ 的数据，$n, U \leq 10^4$，$N,m \leq 10^9$。