Description

We now consider a simplified model. In one round, the bettor needs to predict the results of $n$ matches. Each match’s win-draw-loss outcomes have probabilities $p(i, r)$. Here, $i$ denotes the $i$-th match and $r \in \{0, 1, 2\}$ denotes the home team’s loss, draw, and win, respectively. The value $p(i, r)$ is the probability that match $i$ ends with result $r$. In addition, $q(i, r)$ denotes the probability that, among all purchased bets, result $r$ is chosen for match $i$, i.e., the fraction of the total number of bets that select that outcome for that match.

For example, if $q(1, 0) = 0.5$, then we know that $50\%$ of the bets choose the home team to lose in the first match. We assume these $n$ matches are independent, i.e., the outcomes $p(i, r)$ are independent across matches, and the selections $q(i, r)$ are also independent across matches (with $r \ne r'$).

In this model, a ticket wins only if it correctly predicts all $n$ matches. The total prize pool is $M$ and is shared equally among all winning bets. Therefore, for a single bet $R_i = \{r_{i1}, r_{i2}, \ldots, r_{in}\}$, where $r_{ij}$ is the predicted result of bet $R_i$ for match $j$, its winning probability is:

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

Let the total number of bets be $N$. Then the total number of winning bets is:

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

Hence, the expected prize (the average prize) received by bet $R_i$ is:

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

The above only considers single bets, i.e., the winning of a single $R_i$. For multiple bets, the situation is more complicated. A multiple bet is a set $R = \{R_1, R_2, \ldots, R_k\}$, where $k$ is the number of bets. For example, with three matches, if the first match is “win or loss,” the second is “draw,” and the third is “loss or draw,” then $k = 4$, and the set $R$ contains the following four elements:

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

In a multiple bet $R$, you win if at least one $R_i$ predicts all results correctly. Therefore, the expected prize of $R$ is:

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

The problem: given the information for $n$ matches (the probabilities of outcomes and the probabilities that bettors buy those outcomes), and the maximum number of bets $U$ allowed in a multiple bet, design a multiple betting scheme that does not exceed the maximum number of bets ($k \le U$) and maximizes the expected prize.

Input Format

The first line contains four positive integers $n, N, M, U$, where $n, U \le 10^4$ and $N, M \le 10^9$.

Each of the next $n$ lines contains six real numbers. The six real numbers on line $i + 1$ are $p(i, 0), p(i, 1), p(i, 2), q(i, 0), q(i, 1), q(i, 2)$, describing match $i$. Here, $p(i, 0) + p(i, 1) + p(i, 2) = 1$, $q(i, 0) + q(i, 1) + q(i, 2) = 1$, and $q(i, j) \ne 0$.

Output Format

Output a real number, the natural logarithm of the maximum expected prize:

$$\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).$$

Print the answer with $3$ decimal places (rounded half up).

1 10 10 1
0.3 0.2 0.5 0.7 0.2 0.1

1.609

Hint

Translated by ChatGPT 5