В фирму Никиты набрали n человек. Теперь ему нужно построить древовидную иерархию отношений «начальник-подчинённый» в этой фирме (то есть у каждого человека, кроме одного, должен быть ровно один начальник). Дано m заявлений вида «человек ai готов стать начальником человека bi за дополнительную плату ci». Для каждого человека известно его значение квалификации qj, и для каждого заявления выполняется условие qai > qbi.
Помогите Никите определить минимальную стоимость создания иерархии, либо выяснить, что это невозможно.
Выходные данные
В единственной строке выходных данных выведите минимальную стоимость создания иерархии или -1, если создать иерархию невозможно.
Примечание
В первом примере один из возможных вариантов составления иерархии — взять заявления под номерами 1, 2 и 4, которые в сумме дадут стоимость 11. Во втором примере составить иерархию невозможно, поэтому ответ -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7 2 3 1
4
1 2 5
2 4 1
3 4 1
1 3 5
|
11
|
|
2
|
3
1 2 3
2
3 1 2
3 1 3
|
-1
|