Мальчик Геральд зашел в магазин одежды, и обнаружил неприятную вещь: оказывается, не вся одежда подходит друг к другу. Например, Геральд заметил, что в смокинге и кепке он смотрится довольно нелепо.
Всего в магазине продается n элементов одежды, и ровно m пар одежек подходят друг другу. Каждый элемент одежды имеет цену, которая выражается целым числом рублей. Геральд хочет купить себе три элемента одежды так, чтобы они подходили друг другу, и потратить при этом как можно меньше денег. Найдите минимальную сумму, которую он может потратить.
Выходные данные
Выведите единственное число — минимальную сумму в рублях, которую Геральду придется потратить в магазине, или «-1» (без кавычек), если нет трех элементов одежды, подходящих друг к другу.
Примечание
В первом тесте есть всего три одежки, и они все подходят друг к другу. Соответственно, есть единственный вариант купить 3 одежки, и в этом случае он потратит 6 рублей.
Во втором тесте тоже всего три одежки, но Геральд не может их купить, потому что первая одежка не подходит к третьей. Таким образом, нет трех подходящих друг к другу одежек. Ответ -1.
В третьем примере 4 одежки, но никакие 3 из них Геральд не может купить одновременно. Ответ -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 3
1 2
2 3
3 1
|
6
|
|
2
|
3 2
2 3 4
2 3
2 1
|
-1
|
|
3
|
4 4
1 1 1 1
1 2
2 3
3 4
4 1
|
-1
|