← 返回题目列表

Codeforces · 616/B

B. 与艾玛共进晚餐

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

杰克决定邀请艾玛出去吃晚饭。杰克是一个谦虚的学生,他不想去昂贵的餐馆。艾玛是一个有高品味的女孩,她更喜欢精英场所。

Munhattan 由 n 条街道和 m 条大道组成。每条街道和大道的交叉口都只有一家餐馆。街道用 1 到 n 的整数编号,大道用 1 到 m 的整数编号。在第i条街和第j条大道交叉口的餐厅吃饭的费用是cij。

杰克和艾玛决定按以下方式选择餐厅。首先艾玛选择了吃饭的街道,然后杰克选择了大道。艾玛和杰克做出了最佳选择:艾玛想要最大化晚餐的成本,杰克想要最小化它。艾玛考虑到杰克想尽量减少晚餐的费用。计算热恋中情侣的晚餐费用。

输入

第一行包含两个整数 n, m (1 ≤ n, m ≤ 100) — Munhattan 的街道和大道的数量。

接下来的 n 行每行包含 m 个整数 cij (1 ≤ cij ≤ 109) — 第 i 条街和第 j 条大道交叉口的餐厅的晚餐费用。

输出

打印唯一的整数a——杰克和艾玛的晚餐费用。

示例

输入 #1

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

输出 #1

2

输入 #2

3 3
1 2 3
2 3 1
3 1 2

输出 #2

1

注意

在第一个示例中,如果艾玛选择第一条街或第三条街,杰克可以选择一条晚餐费用为 1 的大道。因此,她选择第二条街,杰克选择任何大道。晚餐费用是2。

在第二个示例中,无论艾玛的选择如何,杰克都可以选择晚餐费用为 1 的餐厅。