该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE

输入：gift.in

输出：gift.out

题目描述

Vlad 有 $n$ 个朋友，他想为其中的每一个人都买一份新年礼物。

城里有 $m$ 家商店，在每家商店里，他都可以为他的任何一个朋友买礼物。如果第 $j$ 个朋友（$1 \le j \le n$）收到了在第 $i$ 号商店（$1 \le i \le m$）购买的礼物，那么这个朋友将获得 $p_{ij}$ 单位的快乐值。输入的矩形表格中给出了 $p_{ij}$ 的值。

Vlad 最多有时间光顾 $n-1$ 家商店（其中 $n$ 是朋友的数量）。他可以决定去哪些商店，以及在每家商店里为哪些朋友买礼物。

设第 $j$ 个朋友从 Vlad 的礼物中获得了 $a_j$ 单位的快乐。让我们找到值 $\alpha = \min\{a_1, a_2, \dots, a_n\}$。Vlad 的目标是购买礼物，使得 $\alpha$ 的值尽可能大。换句话说，Vlad 想要最大化所有朋友中快乐值的最小值。

例如，假设 $m = 2, n = 2$。在第一家商店可以购买的礼物带给朋友的快乐值为：$p_{11} = 1, p_{12} = 2$；在第二家商店为：$p_{21} = 3, p_{22} = 4$。

在这种情况下，Vlad 只需要去第二家商店，为第一个朋友买礼物（快乐值 3），为第二个朋友买礼物（快乐值 4）。此时 $\alpha$ 的值将等于 $\min\{3, 4\} = 3$。

请帮助 Vlad 为他的朋友们选择礼物，使 $\alpha$ 的值尽可能高。请注意，每个朋友都必须收到一份礼物。Vlad 最多只能访问 $n-1$ 家商店。在一家商店里，他可以购买任意数量的礼物。

输入格式

输入的第一行包含整数 $m$ 和 $n$（$2 \le n, 2 \le n \cdot m \le 10^5$），由空格隔开 —— 分别是商店的数量和朋友的数量，其中 $n \cdot m$ 是 $n$ 和 $m$ 的乘积。

接下来是 $m$ 行，每行包含 $n$ 个数字。第 $i$ 行第 $j$ 列的数字 $p_{ij}$（$1 \le p_{ij} \le 10^9$）是第 $i$ 号商店中为第 $j$ 号朋友准备的商品的快乐值。

输出格式

输出 $\alpha$ 的最大可能值，其中 $\alpha$ 是所有朋友收到礼物的快乐值中的最小值。

输入输出样例

2 2
1 2
3 4

4 3
1 3 1
3 1 1
1 2 2
1 1 3

2 3
5 3 4
2 5 1

4 2
7 9
8 1
9 6
10 8

2 4
6 5 2 1
7 9 7 2

3

2

4

8

2