E. Double trios
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Sam changed his school and on the first lesson of biology he got a very interesting task about genes.

You are given with $$$n$$$ arrays, $$$i$$$-th of which contains $$$m$$$ different integers  — $$$a_{i_1}, a_{i_2},\ldots,a_{i_m}$$$, and also an array of integers $$$w$$$ of length $$$n$$$.

Find the minimum value of expression $$$w_i + w_j$$$ among all pairs of integers $$$(i, j)$$$ such, that in array $$$a_{i_1}, a_{i_2},\ldots,a_{i_k}, a_{j_1}, a_{j_2},\ldots,a_{j, k}$$$ of length $$$2 \cdot m$$$ all the numbers are different ($$$1 \le i, j \le n$$$).

Input

In the first line you are given 2 integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5, 1 \le m \le 5$$$).

In the next $$$i$$$-th of the next $$$n$$$ lines there are $$$m + 1$$$ integers  — $$$a_{i}$$$, $$$1\leq a_{i_j} \leq 10^9$$$ and $$$w_{i}$$$, $$$1 \leq w_{i} \leq 10^9$$$.

Output

Print a single number  — the answer for the task. If answer does not exist, print $$$-1$$$.

Examples
Input
4 2
1 2 5
4 3 1
2 3 2
4 5 3
Output
5
Input
4 3
1 2 3 5
2 3 4 2
3 4 5 3
1 3 10 10
Output
-1