CF1641D.Two Arrays

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.

萨姆转学了，在第一节生物课上，他得到了一个关于基因的非常有趣的任务。

给你 $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}$ 中的所有数互不相同。

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

第一行包含两个整数 $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$）。

Print a single number — the answer to the problem.

If there are no suitable pairs $(i, j)$, print $-1$.

输出一个数字——即该问题的答案。

如果没有满足条件的数对 $(i, j)$，则输出 $-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)$.

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

在第二个测试用例中，不存在满足条件的数对 $(i, j)$。