← 返回题目列表

Codeforces · 333/D

D. 矩形的特征

中文机器翻译题面 查看原题

Gerald 找到了一个由 n 行和 m 列组成的表。作为长方形桌子方面的著名专家,他立即计算了桌子的属性,即桌子角上的数字中的最小值(四个数字中的最小值)。然而,他不喜欢最终的值——它似乎太小了。为了使这个值更大,他决定对表格进行一些裁剪:删除左侧的一些列和右侧的一些列,以及顶部和底部的一些行。求出经过这样的裁剪后表格的最大属性可以是多少。请注意,表格末尾应至少留有两行和至少两列。从四个边中的每一边裁剪的行或列的数量可以为零。

输入

第一行包含两个空格分隔的整数 n 和 m (2 ≤ n, m ≤ 1000)。以下 n 行描述了该表。这些行的第 i 行列出了以空格分隔的整数 ai, 1, ai, 2, ..., ai, m (0 ≤ ai, j ≤ 109) — 表格第 i 行中的 m 个数字。

输出

打印问题的答案。

示例

输入 #1

2 2
1 2
3 4

输出 #1

1

输入 #2

3 3
1 0 0
0 1 1
1 0 0

输出 #2

0

注意

在第一个测试用例中,Gerald 无法裁剪表格 - 表格仅包含两行和两列。

在第二个测试用例中,如果我们裁剪表格,表格的某些角落单元格中将包含零。而且最初它的角单元中包含两个零,所以答案是 0。