时间限制：1秒　　内存限制：256M

---

【题目描述】

　　每年的CQOI比赛结束后都会组织选手参加一次游玩活动。由于人数众多，通常会把选手分成两队出发。组委会为了和谐，想尽量把比较熟悉的选手分在同一队。我们用“友好度”（一个正整数值）来表示某两位选手之间的熟悉程度，友好度越大，则两名选手越熟悉。而“和谐度”定义为两队中熟悉程度最低的那对选手的友好度。

　　现在告诉你选手数量和一些选手之间的友好度，该如何分队(每组至少1人)，才能让两队的和谐度达到最大。请你来帮助组委会完成这个任务。

【输入格式】

　　第一行为两个正整数 \(n\)，分别选手的数目以及友好度大于 0 的选手对数，选手编号为 \(1~n\)。选手编号为 \(1~n\)。接下来是一个\(n * n\)的矩阵，矩阵的第 \(i\) 行第 \(j\) 列表示选手 \(i\) 和选手 \(j\) 的友好度 \(c\)，当 \(i==j\) 时 \(c=0\)，注意，矩阵一定是斜对称的。

【输出格式】

　　一个整数，表示最大和谐度，某些情况下可能为 0。

【输入输出样例1】

　Input

4
0 12 13 9
12 0 18 5 
13 18 0 15
9 5 15 0

　Output

12

【测试点性质】

　　对对于 50% 分的数据，满足 \(2≤n≤1000\)

【来源】

　　Mr.he