1257 : Energy Distribution

Description

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}\).

Sample

2
0 1
1 0
##CASE##
3
0 2 1
2 0 2
1 2 0

0.250000
##CASE##
0.571429

Hint

Source

Author

FUDAN