Острови#275

Острови

5 секунд

256 мегабайтів

Складна

Ви відвідуєте парк, у якому $N$ островів. З кожного острова $i$ прокладено рівно один міст. Довжина цього мосту позначається $L_{i}$ L_i. Усього у парку $N$ мостів. Хоча кожен міст побудований між двома островами, тепер кожен міст можна перетинати в обох напрямках. Крім того, між кожною парою островів існує унікальний пором, що курсує туди й назад.

Оскільки ви віддаєте перевагу пішим прогулянкам замість поїздок поромом, ви хочете максимізувати суму довжин мостів, якими можете пройти, дотримуючись наведених нижче правил.

Ви можете почати прогулянку з будь-якого острова.
Не можна відвідувати жоден острів більше одного разу.
У будь-який момент ви можете перейти з поточного острова $S$ на інший острів $D$ , який ще не відвідали. Перейти з $S$ на $D$ можна так:
1. Пішки: це можливо, лише якщо між цими островами є міст. У цьому випадку довжина мосту додається до вашого маршруту.
2. Пором: можна скористатися лише якщо неможливо дістатися з $S$ у $D$ будь-якою комбінацією мостів і/або вже використаних поромів (навіть через відвідані острови). Зверніть увагу: не обов'язково відвідати всі острови чи перетнути всі мости.

Дано $N$ мостів та їх довжини. Напишіть програму, яка обчислить максимальну можливу довжину маршруту мостами, дотримуючись описаних правил.

2 \leq N \leq 1000000

2 \leq N \leq 1\,000\,000

1 \leq L_{i} \leq 100000000

1 \leq L_i \leq 100\,000\,000

Вхідні дані

Ваша програма повинна зчитати з вхідного потоку:

У першому рядку ціле число $N$ — кількість островів у парку. Острови пронумеровано від $1$ до $N$ .
Далі $N$ рядків описують мости. $i$ -ий рядок містить два цілих числа, розділених пробілом: перше — номер іншого острова, друге — довжина мосту $L_{i}$ L_i. Кінці кожного мосту — завжди різні острови.

Вихідні дані

Виведіть одне ціле число — максимальну можливу довжину маршруту мостами.

Приклади

Приклад 1

Примітка

Примітка 1. Для деяких тестових даних відповідь може не вміщатися у $32$ -бітне ціле число. Щоб отримати повний бал, використовуйте $in t 64$ у Pascal або $l o n g l o n g$ long~long у C/C++.

Примітка 2. У середовищі тестування $64$ -бітні типи даних у Pascal зчитуються істотно повільніше, ніж $32$ -бітні типи, навіть якщо значення вміщуються у $32$ біти. Рекомендується використовувати для зчитування $32$ -бітні типи. Для деяких випадків на $40$ балів $N$ не перевищує $4000$ .