Problem I
Communication Matters

Satsuki and Mei

Satsuki and Mei both have to guess a secret number. Satsuki is trying to guess $a$ and Mei is trying to guess $b$. Both $a$ and $b$ can take values between $1$ and $n$. Satsuki and Mei know the joint probabilities of their secret numbers being a specific number.

When trying to guess the value of $a$ independently, Satsuki can make a guess in the following form: “Is $a$ in the set $S$?” Here, $S$ is some subset of the natural numbers up to $n$. Satsuki has found the value of $a$ when she is able to narrow down the possibilities to a single number.

For example, if $n = 6$, the value of $a$ is found if the answer to “Is $a$ in the set $\{ 1,2,3,4,5\} $” is “no”.

Mei can do the same with her number.

If Satsuki is working alone and has adopted an optimal strategy to minimize the expected number of guesses, let $x$ be the expected number of guesses for Satsuki to find her number. If Mei is working alone and has adopted an optimal strategy to minimize the expected number of guesses, let $y$ be the expected number of guesses for Mei to find her number.

They believe that by working together, they can get to their numbers faster.

While Mei and Suzuki are working together, the queries now take the form “Is $(a,b)$ in the set $T$?” where $T$ is a subset of the set of tuples $\{ (i,j) \mid 1 \leq i,j \leq n \} $. Let $z$ be the expected number of guesses for Satsuki and Mei to find their number together, given that they have adopted an optimal strategy to minimize the expected number of guesses.

Please find $(x+y) - z$.

Input

The first line of input contains a single integer $n \: (2 \leq n \leq 200)$, denoting that $a$ and $b$ can take integer values between $1$ and $n$ inclusive. After the first line, there follow $n$ lines of input, where each line of input contains $n$ space-separated real numbers. When considering the $i$-th line after the first line, the $j$-th real number on this line will represent the probability $\mathbb P(a=i, b=j)$. Each probability will contain at most $7$ digits after the decimal point.

It is guaranteed that $\sum _{i=1}^n \sum _{j=1}^n \mathbb P(a=i, b=j)=1$ (within an absolute error of $10^{-4}$), and for all $i$ and $j$, $0 \leq \mathbb P(a=i, b=j) \leq 1$.

Output

Output one line containing a single real number $(x+y) - z$. Any answer within an absolute or relative error of $10^{-6}$ will be accepted.

3
0.05 0.1 0.15
0.04 0.03 0.07
0.01 0.05 0.5

0.35

2
0.25 0.25
0.25 0.25

0