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)$$$。