Вова пообещал себе больше никогда не играть в игры... Но недавно компания Firestorm выпустила очень популярную игру — World of Farcraft, и Вова, конечно же, начал в неё играть.
Он впал в ступор при выполнении очередного квеста — необходимо было прийти в поселение Надгород и распространить там слух.
Вова знает, что в Надгороде живут n персонажей. Некоторые персонажи дружат между собой и готовы делиться информацией друг с другом. Также он знает, что i-й персонаж готов начать распространять слух за ci золота. Как только персонаж узнаёт слух, он рассказывает его всем своим друзьям, которые, в свою очередь, тоже начинают распространять этот слух (но уже бесплатно).
Вова хочет, чтобы слух узнали все n персонажей Надгорода. За какое минимальное количество золота он сможет это сделать?
Посмотрите примечание для лучшего понимания задачи.
Выходные данные
Выведите единственное число — минимальное количество золота, за которое Вова сможет выполнить квест.
Примечание
В первом тестовом примере Вове выгоднее всего заплатить первому персонажу (он узнает слух и расскажет его четвёртому персонажу, который в свою очередь расскажет его пятому персонажу). Также ему будет необходимо заплатить второму и третьему персонажам, чтобы они тоже узнали слух.
Во втором тестовом примере необходимо заплатить всем персонажам.
В третьем тестовом примере необходимо заплатить первому, третьему, пятому, седьмому и девятому персонажам, которые расскажут слух своим друзьям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
2 5 3 4 8
1 4
4 5
|
10
|
|
2
|
10 0
1 2 3 4 5 6 7 8 9 10
|
55
|
|
3
|
10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10
|
15
|