题目描述

Jack 决定邀请 Emma 共进晚餐。Jack 是一个谦逊的学生，他不想去昂贵的餐厅。而 Emma 是一个品味很高的女孩，她更喜欢高档场所。

Munhattan 有 $n$ 条街道和 $m$ 条大道。在每条街道和每条大道的交叉口恰好有一家餐厅。街道编号为 $1$ 到 $n$，大道编号为 $1$ 到 $m$。在第 $i$ 条街道与第 $j$ 条大道的交叉口餐厅的晚餐价格为 $c_{ij}$。

Jack 和 Emma 决定以如下方式选择餐厅：首先 Emma 选择用餐的街道，然后 Jack 选择大道。Emma 和 Jack 都会作出最优选择：Emma 希望使晚餐价格最大化，Jack 希望使晚餐价格最小化。Emma 会考虑到 Jack 想要最小化晚餐价格。请你计算这对情侣最终用餐的价格。

输入格式

第一行包含两个整数 $n,m$（$1 \leq n,m \leq 100$），表示 Munhattan 的街道和大道的数量。

接下来的 $n$ 行，每行包含 $m$ 个整数 $c_{ij}$（$1 \leq c_{ij} \leq 10^{9}$），表示第 $i$ 条街道与第 $j$ 条大道交叉口餐厅的价格。

输出格式

输出唯一一个整数 $a$，表示 Jack 和 Emma 的晚餐价格。

说明/提示

在第一个样例中，如果 Emma 选择第一条或者第三条街道，Jack 可以选择价格为 $1$ 的大道。因此她选择第二条街道，Jack 选择任意一条大道，晚餐价格为 $2$。

在第二个样例中，无论 Emma 如何选择，Jack 都可以选择价格为 $1$ 的餐厅。

由 ChatGPT 5 翻译

样例

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

2

3 3
1 2 3
2 3 1
3 1 2

1