Football corruption P84060

Statement

An infamous football club (let us call it $X$ ) wants to buy yet another competition. There are $n$ teams, where $n = 2^m$ for some $m$ . As usual, the tournament scheme is a complete binary tree, so $X$ will have to win $m$ matches to be the champion. The president of $X$ knows, for every pair of teams $i$ and $j$ , the probability $p_{ij}$ that $i$ eliminates $j$ . So he will bribe the football federation, and arrange the play offs so as to maximize the probability that $X$ wins the competition. Can you compute that probability?

Input

Input consists of several cases, each one with $n$ , followed by $n$ lines with $n$ probabilities each, where the $j$ -th number of the $i$ -th line is $p_{ij}$ . Assume $1 \le m \le 3$ , that $p_{ji} = 1 - p_{ij}$ for every $i \ne j$ , and that the diagonal of the matrix has only -1. $X$ is the first team.

Output

For every case, print the probability with four digits after the decimal point. The input cases have no precission issues.

Hint

The expected solution is a “reasonable” backtracking. For instance, 2000 tests with $n=8$ should be solved in at most one second.

Public test cases

Input

2
-1 0.6
0.4 -1

4
 -1   1 0.5   0
  0  -1 0.7 0.8
0.5 0.3  -1 0.1
  1 0.2 0.9  -1

8
 -1 0.1 0.2 0.3 0.4 0.5 0.6 0.7
0.9  -1 0.9 0.8 0.7 0.6 0.5 0.4
0.8 0.1  -1 0.1 0.2 0.3 0.4 0.5
0.7 0.2 0.9  -1 0.5 0.6 0.7 0.8
0.6 0.3 0.8 0.5  -1 0.2 0.4 0.6
0.5 0.4 0.7 0.4 0.8  -1 0.8 0.4
0.4 0.5 0.6 0.3 0.6 0.2  -1 0.3
0.3 0.6 0.5 0.2 0.4 0.6 0.7  -1

Output

0.6000
0.4000
0.1100

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++