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 ≤ m ≤ 3,
that p_{ji} = 1 − p_{ij} for every i ≠ 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++
- Event
- Setzè Concurs de Programació de la UPC - Final
- Date
- 2018-09-19