Maximizing Expected Prize with Multiple Bets

You are given a simplified model of a betting game. In one round of the contest, a bettor has to predict the outcomes of n matches. For each match i (1 ≤ i ≤ n), there are three possible outcomes: loss (0), draw (1), and win (2). The probability that the match i ends with outcome r (r ∈ {0, 1, 2}) is given in \(p(i, r)\), and the probability that a bet on outcome r is purchased is given in \(q(i, r)\) (this is the proportion of total bets placed on that outcome for match i).

A single bet consists of a prediction vector \(R = (r_1, r_2, \ldots, r_n)\), and its winning probability is

[ P(R) = \prod_{j=1}^n p(j, r_j)]

while the proportion of tickets that purchased the combination (R) is

[ Q(R) = \prod_{j=1}^n q(j, r_j).]

If the total number of bets is (N) and the total prize is (M), then if a single bet wins the prize awarded to it is

[ \frac{M}{N \cdot Q(R)} \cdot P(R).]

In a multiple bet (or compound bet) scenario, a bettor chooses a set \(R = \{R_1, R_2, \ldots, R_k\}\) of different single bets. The bet wins if at least one of the selected single bets is entirely correct, and the expected prize is the sum over the selected bets:

[ E = \sum_{R_i \in R} \frac{M}{N \cdot Q(R_i)} \cdot P(R_i) = \frac{M}{N} \sum_{R_i \in R} \frac{P(R_i)}{Q(R_i)}.]

Your task is: given the information for n matches (i.e. the probabilities \(p(i, r)\) and \(q(i, r)\) for each outcome), and a maximum number \(U\) of bets that can be chosen in a multiple bet (i.e. \(k \le U\)), design a betting strategy that maximizes the expected prize. It can be shown that the optimal strategy is to choose the \(U\) (or fewer if the total number of possible combinations is less than \(U\)) single bets with the largest value of

[ \frac{P(R)}{Q(R)} = \prod_{j=1}^n \frac{p(j, r_j)}{q(j, r_j)}.]

Thus, the problem reduces to finding and summing up the top \(U\) values among all possible combinations \(\prod_{j=1}^n \frac{p(j, r_j)}{q(j, r_j)}\), and then multiplying the sum by \(\frac{M}{N}\>.

inputFormat

The first line contains four numbers: n U M N, where n is the number of matches, U is the maximum number of bets allowed in the multiple bet, M is the total prize, and N is the total number of bets.

Then follow n lines, each containing six real numbers: the first three numbers are p(i,0), p(i,1), p(i,2) and the next three numbers are q(i,0), q(i,1), q(i,2) for the ith match. It is guaranteed that for each match, \(p(i,0)+p(i,1)+p(i,2)=1\) and \(q(i,0)+q(i,1)+q(i,2)=1\).

outputFormat

Output a single real number: the maximum expected prize that can be obtained using at most U bets. The answer will be considered correct if its absolute or relative error does not exceed 10^-6.

sample

1 1 100 1000
0.3 0.4 0.3 0.5 0.3 0.2

0.15

</p>