Острови
Ви приїхали у парк, у якому N островів. Від кожного з островів i колись побудували один міст до якогось іншого острову. Довжина такого мосту позначається L_i. Всього у парку N мостів. Хоча всі мости будували від одного острову до іншого, у даний час по кожному з мостів можна рухатись у довільному з двох напрямків. Крім цього, між кожними двома островами ходить один паром як туди, так і назад.
Так як вам більше подобається ходити по мостам, ніж їздити на паромі, ви хочете максимізувати сумарну довжину мостів, по яким ви пройдете. При цьому необхідно враховувати наступне:
Починати рух можна з довільного з островів за вашим вибором.
Забороняється відвідувати який-небудь з островів більше одного разу.
В довільний момент ви можете переміститись з острову S, на якому ви заходитесь, на інший остров D, який ви ще не відвідували. Ви можете попасти з S на D наступним чином:
Пішки: це можливо, якщо між двома островами є міст. У цьому випадку довжина мосту додається до довжини раніше пройденого шляху.
Паромом: ви можете скористатись цим способом лише у тому випадку, якщо острів D не можна досягнути з острова S при допомозі якої-небудь комбінації мостів і/або використаних раніше паромів. При перевірці можливсоті досягнення острова D з острова S слід розглядати всі можливі шляхи, включаючи шляхи, що проходять через острови, на яких ви вже були. Зверніть увагу, що немає необхідності відвідувати всі острови, і може бути, ще неможливо пройти по всім мостам.
Напишіть програму, яка за заданими N мостами та їх довжинами обчислює максимальну довжину шляху, що задовільняє умовам, описаним вище. Довжина шляху визначається як сумарна довжина пройдених мостів. 2 <= N <= 1 000 000 (N – кількість островів у парку) 1 <= L_i <= 100 000 000 (L_i – довжина i-го мосту)
Вхідні дані
Ваша програма читає зі стандартного вводу наступні дані:
Рядок 1 містить ціле число N – кількість островів у парку. Острови пронумеровані від 1 до N включно.
Кажен з наступних N рядків описує один міст, при цьому i-ий рядок містить два цілих числа, відокремлених одним пропуском. Ці два числа описують міст, побудований від i-го острову. Перше число – это номер острову, до якого будувався міст. Друге число – це довжина мосту L_i. Ви можете вважати, що кінці довільного мосту знаходяться на різних островах.
Вихідні дані
Ваша програма повинна вивести у стандартний вивід єдиний рядок, шо містить одне ціле число – максимальну довжину шляху, який можна пройти.
Зауваження 1. Для деяких з тестів відповідь не може бути обрахована з використанням 32-бітного цілого типу. Щоб отримати повний бал по цій задачі, вам потрібно використовувати тип int64 у мові Паскаль або тип long long у мові C/C++.
Зауваження 2. При запуску програми на мові Паскаль у середовищі системи тестування, 64-бітні цілі типи даних читаються зі стандартного потоку вводу набагато повільніше, ніж 32-бітні цілі типи даних, навіть якщо зчитувані значення поміщаються у 32-бітний цілий тип. Ми рекомендуємо вам використовувати при зчитуванні даних 32-бітний цілий тип.