问题说明

有 n(3≤n≤200) 个人，他们彼此之间都有一个默契值，我们用 ai,j 表示第 i 个人和第 j 个人之间的默契值。

现在需要从 n 个人中选出三个人去参加一个比赛，三个人的默契程度等于这三个人两两之间的默契值的最小值。你希望选出的三个人的默契程度尽可能地大。

求最大的默契程度。

输入格式

输入的第一行包含一个整数 n(3≤n≤200)。

接下来 n 行，每行包含 n 个整数，其中第 i 行的第 j 个整数表示第 i 个人和第 j 个人之间的默契值 ai,j。

数据保证对于任意 1≤i≤n 有 a_i,i=0，且对于任意 i≠j 有 a_i,j=a_j,i。

输出格式

5
0 6 2 4 6
6 0 3 1 4
2 3 0 3 5
4 1 3 0 3
6 4 5 3 0

4

提示

样例解释：

选择第 1,2,5 个人，对应的默契程度为 mina1,2,a2,5,a5,1=min6,4,6=4。

数据规模与约定：

• 对于 30 的数据，3≤n≤10,1≤ai,j≤100；
• 对于 60 的数据，3≤n≤50,1≤ai,j≤1000；
• 对于 100 的数据，3≤n≤200,1≤ai,j≤105。

来源/分类