Вы руководите мобильным оператором и хотите предлагать конкурентоспособные цены для создания сети.
В сети есть \(n\) узлов.
Ваш конкурент уже предложил некоторые подключения между узлами по некоторым фиксированным ценам. Эти подключения двусторонние. Всего ваш конкурент предложил \(m\) подключений. \(i\)-е из этих подключений соединяет узлы \(fa_i\) и \(fb_i\) и стоит \(fw_i\).
У вас есть список из \(k\) подключений, которые вы хотите предложить. Гарантируется, что эти подключения не образуют ни одного цикла. \(j\)-е из этих подключений соединит вершины \(ga_j\) и \(gb_j\). Эти подключения тоже двусторонние. Вы еще не определились с ценой каждого из подключений.
Вы можете выбрать стоимости этих подключений любыми целыми числами независимо для каждого из подключений. После этого клиент выберет \(n - 1\) такое подключение из предложенных вами и вашим конкурентом, что все узлы будут объединены в единую сеть, а суммарная стоимость данных подключений будет минимальна. Если существует несколько способов сделать такой выбор, клиент выберет такой, где число ваших подключений максимально.
Вы хотите предложить такие цены, что клиент выберет все \(k\) ваши подключения, а суммарная стоимость этих подключений максимально возможная.
Выведите эту максимально возможную суммарную стоимость, или \(-1\), если она не ограничена.
Выходные данные
Выведите единственное число — максимально возможную прибыль, если вы можете произвольно выбирать стоимости ваших подключений. Если прибыль неограничена, выведите \(-1\).
Примечание
В первом примере оптимально дать стоимость \(3\) подключению \(1-3\), стоимость \(3\) подключению \(1-2\), стоимость \(8\) подключению \(3-4\). В таком случае самый дешевый способ получить связную сеть стоит \(14\), и клиент из таких способов выберет тот, которые содержит все ваши подключения.
Во втором примере до тех пор, пока ваше первое подключение стоит \(30\) или меньше, клиент будет вынужден выбрать оба ваших подключения независимо от цены второго, и вы можете получить неограниченную прибыль.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3 6
1 2
3 4
1 3
2 3 3
3 1 4
1 2 4
4 2 8
4 3 8
4 1 10
|
14
|
|
2
|
3 2 1
1 2
2 3
1 2 30
|
-1
|
|
3
|
4 3 3
1 2
1 3
1 4
4 1 1000000000
4 2 1000000000
4 3 1000000000
|
3000000000
|