D. Два массива
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Стас перешел в новую школу «75-угольник», и на первом же уроке биологии начал умничать, за что его учитель попросил решить задачу по генетике, решение которой сам не знает.

Вам дано $$$n$$$ массивов, $$$i$$$-й из которых содержит $$$m$$$ различных целых чисел — $$$a_{i,1}, a_{i,2},\ldots,a_{i,m}$$$. Также дан массив положительных целых чисел $$$w$$$ длины $$$n$$$.

Вам надо найти минимальное возможное значение выражения $$$w_i + w_j$$$ среди всех пар целых чисел $$$(i, j)$$$ ($$$1 \le i, j \le n$$$) таких, что среди чисел $$$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$$$).

В $$$i$$$-й из следующих $$$n$$$ строк сначала находится $$$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$$$.

Примеры
Входные данные
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
Примечание

В первом тесте минимальное значение это $$$5 = w_3 + w_4$$$, так как среди чисел $$$\{2, 3, 4, 5\}$$$ все различны.

Во втором тесте нет ни одной подходящей пары $$$(i, j)$$$.