| Codeforces Beta Round 79 (Div. 2 Only) |
|---|
| Закончено |
Мальчик Геральд зашел в магазин одежды, и обнаружил неприятную вещь: оказывается, не вся одежда подходит друг к другу. Например, Геральд заметил, что в смокинге и кепке он смотрится довольно нелепо.
Всего в магазине продается n элементов одежды, и ровно m пар одежек подходят друг другу. Каждый элемент одежды имеет цену, которая выражается целым числом рублей. Геральд хочет купить себе три элемента одежды так, чтобы они подходили друг другу, и потратить при этом как можно меньше денег. Найдите минимальную сумму, которую он может потратить.
В первой строке входного файла заданы целые числа n и m — количество одежек, которые продаются в магазине и количество пар одежек, которые подходят друг к другу (
).
В следующей строке даны n целых чисел ai (1 ≤ ai ≤ 106) — стоимости одежек в рублях.
В следующих m строках заданы по одной паре целых чисел ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi) через пробел. Каждая такая пара чисел означает, что ui-тая и vi-тая одежки подходят друг к другу. Гарантируется, что в каждой паре vi и ui различны и все неупорядоченные пары (ui, vi) различны.
Выведите единственное число — минимальную сумму в рублях, которую Геральду придется потратить в магазине, или «-1» (без кавычек), если нет трех элементов одежды, подходящих друг к другу.
3 3
1 2 3
1 2
2 3
3 1
6
3 2
2 3 4
2 3
2 1
-1
4 4
1 1 1 1
1 2
2 3
3 4
4 1
-1
В первом тесте есть всего три одежки, и они все подходят друг к другу. Соответственно, есть единственный вариант купить 3 одежки, и в этом случае он потратит 6 рублей.
Во втором тесте тоже всего три одежки, но Геральд не может их купить, потому что первая одежка не подходит к третьей. Таким образом, нет трех подходящих друг к другу одежек. Ответ -1.
В третьем примере 4 одежки, но никакие 3 из них Геральд не может купить одновременно. Ответ -1.
