← 返回题目列表

Codeforces · 1288/D

D. 极小极大问题

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

给你 $$$n$$$ 数组 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$;每个数组都由 $$$m$$$ 个整数组成。我们将第 $$$x$$$ 数组的第 $$$y$$$ 元素表示为 $$$a_{x, y}$$$。

你必须选择两个数组$$$a_i$$$和$$$a_j$$$($$$1 \le i, j \le n$$$,有可能$$$i = j$$$)。之后,您将获得一个由 $$$m$$$ 整数组成的新数组 $$$b$$$,这样对于每个 $$$k \in [1, m]$$$ $$$b_k = \max(a_{i, k}, a_{j, k})$$$。

您的目标是选择 $$$i$$$ 和 $$$j$$$,以便 $$$\min \limits_{k = 1}^{m} b_k$$$ 的值尽可能最大。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 8$$$) — 分别是数组的数量和每个数组中元素的数量。

接下来是 $$$n$$$ 行,第 $$$x$$$ 行包含由 $$$m$$$ 整数表示的数组 $$$a_x$$$ $$$a_{x, 1}$$$, $$$a_{x, 2}$$$, ..., $$$a_{x, m}$$$ ($$$0 \le a_{x, y} \le 10^9$$$)。

输出

打印两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$, 可能 $$$i = j$$$) — 您必须选择的两个数组的索引,以便 $$$\min \limits_{k = 1}^{m} b_k$$$ 的值尽可能最大。如果有多个答案,请打印其中任何一个。

示例

输入 #1

6 5
5 0 3 1 2
1 8 9 1 3
1 2 3 4 5
9 1 0 3 7
2 3 0 6 3
6 4 1 7 0

输出 #1

1 5