Two Arrays

题意翻译

给定 $n$ 个序列，每个序列中包含 $m$ 个互不相同的数 $a_{i,1},a_{i,2},\ldots,a_{i,m}$ 和一个权值 $w_i$。 你需要找到其中的两个序列 $i$ 和 $j$，使得 $a_{i,1},a_{i,2},\ldots,a_{i,m},a_{j,1},a_{j,2},\ldots,a_{j,m}$ 这 $2 m$ 个数互不相同，且 $w_i+w_j$ 最小。 如果无解，输出 $-1$。

题目描述

Sam changed his school and on the first biology lesson he got a very interesting task about genes. You are given $ n $ arrays, the $ i $ -th of them contains $ m $ different integers — $ a_{i,1}, a_{i,2},\ldots,a_{i,m} $ . Also you are given an array of integers $ w $ of length $ n $ . Find the minimum value of $ w_i + w_j $ among all pairs of integers $ (i, j) $ ( $ 1 \le i, j \le n $ ), such that the numbers $ a_{i,1}, a_{i,2},\ldots,a_{i,m}, a_{j,1}, a_{j,2},\ldots,a_{j,m} $ are distinct.

输入输出格式

输入格式

The first line contains two integers $ n $ , $ m $ ( $ 2 \leq n \leq 10^5 $ , $ 1 \le m \le 5 $ ). The $ i $ -th of the next $ n $ lines starts with $ m $ distinct integers $ a_{i,1}, a_{i,2}, \ldots, a_{i,m} $ and then $ w_i $ follows ( $ 1\leq a_{i,j} \leq 10^9 $ , $ 1 \leq w_{i} \leq 10^9 $ ).

输出格式

Print a single number — the answer to the problem. If there are no suitable pairs $ (i, j) $ , print $ -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

说明

In the first test the minimum value is $ 5 = w_3 + w_4 $ , because numbers $ \{2, 3, 4, 5\} $ are distinct. In the second test case, there are no suitable pair $ (i, j) $ .