问题 4763 --买礼物

4763: 买礼物★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 48  解决: 34
[提交][状态][命题人:]

题目描述

琪琪有n个朋友,他想给他们每人买个新年礼物。

城市里有m个商店,在每个商店他可以买一个礼物送给任一个朋友。如果第j(1=<j<=n)个朋友收到第i(1<=i<=m)个商店的礼物,他就获得pij单元的乐趣,输入会给出pij的矩阵。

琪琪最多有时间访问n-1个商店。设第j个朋友收到aj单元的乐趣,设价值A=min{a1,a2,......,an}。

琪琪的目标是让A尽可能大。

例如:m=2,n=2.第一个商店的乐趣单元为:p11=1,p12=2;第二个商店的为:p21=3,p22=4.

此时琪琪只需去第二个商店买两个礼物,A=min{3,4}=3.

请你帮琪琪买礼物,注意,在商店里琪琪可买任意多的礼物。

输入

第一行为t(1<=t<=10000)为数据组数。每组数据前空一行,接下来一行包含m和n(2=<n,2=<n*m<=100000),表示商店数和朋友数。接下来m行,每行包括n个数,第i行第j列
为pij(1=<pij<=1000000000)。保证每组数据n*m不超过100000.

输出

t行,每行为每组数据的答案:A的最大值
样例输入
Copy
5

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
样例输出
Copy
3
2
4
8
2

提示

来源

[提交][状态]