← 返回题目列表

Codeforces · 1641/D

D. 两个数组

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

Sam 换了学校,在第一节生物课上,他得到了一个关于基因的非常有趣的任务。

给定 $$$n$$$ 数组,其中第 $$$i$$$ 包含 $$$m$$$ 不同的整数 — $$$a_{i,1}, a_{i,2},\ldots,a_{i,m}$$$。此外,您还会获得一个长度为 $$$n$$$ 的整数数组 $$$w$$$。

找出所有整数对 $$$(i, j)$$$ ($$$1 \le i, j \le n$$$) 中 $$$w_i + w_j$$$ 的最小值,使得数字 $$$a_{i,1}, a_{i,2},\ldots,a_{i,m}, a_{j,1}, a_{j,2},\ldots,a_{j,m}$$$ 是不同的。

输入

第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \le m \le 5$$$)。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 行以 $$$m$$$ 不同的整数 $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ 开头,然后是 $$$w_i$$$ ($$$1\leq a_{i,j} \leq 10^9$$$, $$$1 \leq w_{i} \leq 10^9$$$)。

输出

打印一个数字——问题的答案。

如果没有合适的对 $$$(i, j)$$$,则打印 $$$-1$$$。

示例

输入 #1

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

输出 #1

5

输入 #2

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

输出 #2

-1

注意

在第一个测试中,最小值为 $$$5 = w_3 + w_4$$$,因为数字 $$$\{2, 3, 4, 5\}$$$ 是不同的。

在第二个测试用例中,没有合适的对 $$$(i, j)$$$。