H. Energy Distribution
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ planets in the galaxy. Some undirected tunnels connect planets. There exists at most one tunnel connecting each pair of planets. So these tunnels can be described as an $$$n\times n$$$ matrix $$$W_{n\times n}$$$. Specifically, the tunnel connecting planet $$$i$$$ and $$$j$$$ has a width of $$$w_{i,j}$$$(If there is no tunnel between planet $$$i$$$ and $$$j$$$, then $$$w_{i,j}=0$$$).

Now, you want to distribute exactly $$$1.0$$$ unit of energy among the $$$n$$$ planets. Suppose that planet $$$i$$$ is distributed $$$e_i$$$(a real number) unit of energy ($$$e_i\ge 0, \sum_{i=1}^ne_i=1$$$), these planets will bring $$$E$$$ magical value, where $$$E = \sum_{i=1}^n\sum_{j=i+1}^ne_ie_jw_{i,j}$$$.

Please distribute the energy and maximize the magical value.

Input

The first line contains an interger $$$n(1\le n\le 10)$$$.

For the next $$$n$$$ lines, each line contains $$$n$$$ intergers. The $$$j$$$-th integer in the $$$i$$$-th line is $$$w_{i,j}(0\le w_{i,j}\le 1000)$$$. Indicating the matrix $$$W_{n\times n}$$$.

Output

Output a real number as the answer. If your answer is $$$A$$$ while the standard answer is $$$B$$$, your answer will be accepted if and only if $$$\frac{|A-B|}{\max(|A|,1)} \le 10^{-6}$$$.

Examples
Input
2
0 1
1 0
Output
0.250000
Input
3
0 2 1
2 0 2
1 2 0
Output
0.571429