题目描述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

出题Author

FUDAN

来源Source