题目描述

为了帮助柯南回到一米七四，阿笠博士夜以继日地研究 APTX4869 的解药。他得出了如下结果：

\(1.\) 解药由 \(n\) 种原料构成；

\(2.\) 对于两种不同的的原料 \(a,b\)，它们之间有个影响值 \(f(a,b)\)；

\(3.\) 需要把所有原料分成两部分 \(X,Y\)，每部分中至少有一种原料；

\(4.\) 解药的效果由分别属于 \(X,Y\) 的原料之间，最小的影响值决定，即

效果=\(min\{f(a,b)|a∈X,b∈Y\}\)

博士需要你帮忙求出：在所有的方案中，最大的效果值可以是多少？

格式

输入格式

多组数据 \((<=10)\)，处理到 \(EOF\)。

每组数据输入第一行为一个正整数 \(n\)。

接下去是一个 \(n\) 行 \(n\) 列的整数矩阵，同一行的数以空格隔开。矩阵第 \(i\) 行 \(j\) 列表示第 \(i\) 种和第 \(j\) 种材料的影响值 \(f(i,j)\)。给出的矩阵是对称的，即 \(f(i,j)=f(j,i)\)。当 \(i=j\) 时，\(f(i,i)\) 没有意义，矩阵该处的值为 \(-1\)。

输出格式

每组数据输出一行，表示最大可能的效果值。

样例1

样例输入1

3
-1 100 300
100 -1 200
300 200 -1

样例输出1

200

限制

时间：\(1s\) 空间：\(64M\)

\(2<=n<=800。\)当 \(i!=j\) 时，\(0<=f(i,j)<=1,000,000\)；当 \(i=j\) 时，\(f(i,j)=-1\)。

来源

地址：\(zloj,J2020\)域
作者：\(jialiang2509\)
模拟赛 \(T2\)