Codeforces Round 773 (Div. 1) |
---|
Закончено |
Стас перешел в новую школу «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)$$$.
Название |
---|