Острова
Вы приехали в парк, в котором n островов. От каждого из островов i когда-то построили один мост до какого-то другого острова. Длина такого моста обозначается L_i. Всего в парке n мостов. Хотя все мосты строили от одного острова до другого, в настоящее время по каждому мосту можно двигаться в любом из двух направлений. Помимо этого, между каждыми двумя островами ходит один паром как туда, так и обратно.
Так как вам больше нравится ходить по мостам, чем ездить на пароме, вы хотите максимизировать суммарную длину мостов, по которым вы пройдете. При этом необходимо учитывать следующее:
Начать движение можно с любого из островов по вашему выбору.
Запрещается посещать какой-либо из островов более одного раза.
В любой момент вы можете переместиться с острова s, на котором вы находитесь, на другой остров d, который вы еще не посещали. Вы можете попасть с s на d следующим образом:
Пешком: это возможно, если между двумя островами есть мост. В этом случае длина моста добавляется к длине ранее пройденного пути.
Паромом: вы можете воспользоваться этим способом только в том случае, если остров d не достижим c острова s с помощью какой-либо комбинации мостов и/или использованных ранее паромов. При проверке достижимости острова d c острова s следует рассматривать все возможные пути, включая пути, проходящие через острова, на которых вы уже были. Обратите внимание, что нет необходимости посещать все острова, и может быть невозможно пройти по всем мостам.
Напишите программу, которая по заданным n мостам и их длинам вычисляет максимальную длину пути, удовлетворяющего вышеописанным условиям. Длина пути определяется как суммарная длина пройденных мостов.
Входные данные
Первая строка содержит количество островов n (1 ≤ n ≤ 10^6) в парке. Острова пронумерованы от 1 до n включительно. Каждая из последующих n строк описывает один мост, при этом i-я строка содержит два целых числа, разделенных одним пробелом. Эти два числа описывают мост, построенный от i-го острова. Первое число - это номер острова, до которого строился мост. Второе число - это длина моста L_i (1 ≤ L_i ≤ 10^8). Вы можете считать, что концы любого моста находятся на различных островах.
Выходные данные
Вывести одно целое число – максимальную длину пути, который можно пройти.
Замечание 1. Для некоторых из тестов ответ не может быть вычислен с использованием 32-битного целого типа. Чтобы получить полный балл по этой задаче, вам потребуется использовать тип int64 в языке Паскаль или тип long long в языке C/C++.
Замечание 2. При запуске программы на языке Паскаль в среде системы тестирования, 64-битные целые типы данных читаются из стандартного потока ввода гораздо медленее, чем 32-битные целые типы данных, даже если читаемые значения помещаются в 32-битный целый тип. Мы рекомендуем вам использовать для чтения данных 32-битный целый тип.