← 返回题目列表

Codeforces · 1619/D

D. 新年问题

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

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$$$ 的价值尽可能大。换句话说,弗拉德想要最大化他朋友们最小的快乐。

例如,让$$$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$$$ 商店(其中 $$$n$$$ 是朋友的数量)。在商店里,他可以购买任意数量的礼物。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。

每个测试用例之前写入一个空行。然后有一行包含整数 $$$m$$$ 和 $$$n$$$ ($$$2 \le n$$$, $$$2 \le n \cdot m \le 10^5$$$),并用空格分隔 — 商店数量和朋友数量,其中 $$$n \cdot m$$$ 是 $$$n$$$ 和 $$$m$$$ 的乘积。

接下来是 $$$m$$$ 行,每行包含 $$$n$$$ 数字。 $$$j$$$第$$$p_{ij}$$$第$$$i$$$行的数字($$$1\le p_{ij}\le 10^9$$$)是$$$i$$$店号中给朋友$$$j$$$预定的商品的喜悦度。

保证测试中所有测试用例的值 $$$n \cdot m$$$ 之和不超过 $$$10^5$$$。

输出

打印 $$$t$$$ 行,每行必须包含相应测试用例的答案 - $$$\alpha$$$ 的最大可能值,其中 $$$\alpha$$$ 是给 Vlad 所有朋友的礼物带来的最小快乐。

示例

输入 #1

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

输出 #1

3
2
4
8
2