Optimizing Tournament Bracket for Maximum Expected Reward

With the upcoming Olympics and a surge in sports enthusiasm, the school is organizing a table tennis tournament in a knockout format. There are n participants, where n is a power of 2 (n = 2^k). Each participant is assigned a unique number from 1 to n and the tournament bracket is fixed in the usual knockout style. When a player loses, they are eliminated; the loser in round i wins a prize of a_i dollars (for i = 1, 2, …, k) and the champion wins a_k+1 dollars. It is guaranteed that

$$a_1 < a_2 < \cdots < a_{k+1},$$

Small Z (player numbered 1) is a table tennis enthusiast who, after a series of warm-up games, discovered that his defeats were due to unfavorable matchups – his opponents had playing styles that countered his own. In the official tournament, he has the freedom to reassign the positions (i.e. the bracket arrangement) of all players. The match outcome between any two players A and B is given by the probability P_{A,B} that player A beats player B (with the condition that </em>P_A,B + P_B,A = 1</em>).

Help small Z arrange the tournament bracket so that his expected prize is maximized. Under the chosen bracket, if small Z plays opponents with winning probabilities q₁, q₂, …, q_k in rounds 1 through k respectively, his expected prize is given by:

$$E = a_{k+1} \prod_{i=1}^{k}q_i + \sum_{i=1}^{k} a_i\Big(\prod_{j=1}^{i-1}q_j\,(1 - q_i)\Big). $$

Because small Z can arrange the bracket arbitrarily, he can select for each round the opponent he faces. Notice that if in the tournament he faces extremely tough opponents early then his chance to progress is lower but he still secures the (relatively lower) elimination bonus. On the other hand, if he faces relatively weaker opponents at later stages, his chance to win the champion prize increases. It turns out that the optimal strategy is to choose k opponents for small Z from the other n - 1 players so that their winning probabilities P_{1,j} (for player 1) are as high as possible; then order them in increasing order so that the easier match (with a higher win probability) comes later.

Your task is to compute the maximum expected prize for small Z if you arrange the opponents optimally.

inputFormat

The input consists of:

1. An integer k (1 ≤ k), where n = 2^k is the number of players.
2. k+1 space‐separated numbers: a₁, a₂, …, a_k+1 (the prize for elimination in rounds 1 to k and the champion prize), satisfying a₁ < a₂ < … < a_k+1.
3. n lines follow, each containing n floating–point numbers. The j-th number in the i-th line represents P_i,j, the probability that player i beats player j. It is guaranteed that for all i ≠ j, P_i,j + P_j,i = 1, and you may assume P_i,i = 0 for all i.

Player 1 is small Z.

outputFormat

Output a single floating–point number: the maximum expected prize for small Z. It is recommended to output the answer rounded to at most 6 decimal places.

sample

2
1 2 3
0 0.9 0.8 0.7
0.1 0 0.5 0.6
0.2 0.5 0 0.4
0.3 0.4 0.6 0

2.520000

</p>