题目描述

Mr.lai有n个学生，他想为每个学生准备一份学习资料。

城市中有m家书店，每家书店都可以为他的任何学生购买学习资料。如果第j个学生（1≤j≤n）收到在第i家书店（1≤i≤m）购买的学习资料，那么该学生会获得一定单位的知识提升。输入中给出了表格pij，表示第i家书店的书能给第j个学生提升pij点知识（李明的学生总是能把学习资料读完，所以总是能获得知识提升）。

Mr.lai最多有时间访问n-1家书店（其中n是学生的数量）。他选择他将访问哪些书店以及为哪些学生在每家书店购买学习资料。

假设第j个学生从Mr.lai明的学习资料中获得aj单位的知识提升。我们找到值α=min{a1,a2,…,an}。李明的目标是准备学习资料，使得α的值尽可能大。换句话说，李明希望最大化他的学生们知识提升的最小值。

例如，假设m=2，n=2。假设我们在第一家书店可以购买的学习资料带来的知识提升为：p11=1，p12=2，在第二家书店为：p21=3，p22=4。

那么Mr.lai只需去第二家书店，为第一个学生购买带来3点知识提升的学习资料，为第二个学生购买带来4单位知识提升的学习资料。在这种情况下，α的值将等于min{3,4}=3。

请帮助Mr.lai为他的学生们选择学习资料，使得α的值尽可能高。请注意，每个学生必须收到一份学习资料。李明最多可以访问n-1家书店（其中n是学生的数量）。在书店中，他可以购买任意数量的学习资料。

输入格式

第一行包含两个整数 m 和 n（2≤n，2≤n⋅m≤10^5），用空格分隔——分别是书店的数量和学生的数量，其中 n⋅m 是 n 和 m 的乘积。

接下来是 m 行，每行包含 n 个数字。第 i 行第 j 列的数字 pij（1≤pij≤10^9）表示在第 i 家书店为第 j 位学生提供的知识提升值。

保证所有测试用例中 n⋅m 的总和不超过 10^5。

输出格式

输出 t 行，每行必须包含对应测试用例的答案——即 α 的最大可能值，其中 α 是Mr.lai的所有学生从礼物中获得的快乐值的最小值。

样例输入1

2 2
1 2
3 4

样例输出1

3

样例输入2

4 2
7 9
8 1
9 6
10 8

样例输出2

8

样例输入3

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

样例输出3

2