#P1641D. Two Arrays

    ID: 6306 Type: RemoteJudge 3000ms 512MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>bitmasksbrute forcecombinatoricsgreedyhashingmathtwo pointers*2700

Two Arrays

No submission language available for this problem.

Description

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

Input

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

Output

Print a single number — the answer to the problem.

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

Samples

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

Note

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