Вы приехали в парк, в котором N островов. От каждого из островов i когда-то построили один мост до какого-то другого острова. Длина такого моста обозначается Li. Всего в парке N мостов. Хотя все мосты строили от одного острова до другого, в настоящее время по каждому мосту можно двигаться в любом из двух направлений. Помимо этого, между каждыми двумя островами ходит один паром как туда, так и обратно.

   Так как вам больше нравится ходить по мостам, чем ездить на пароме, вы хотите максимизировать суммарную длину мостов, по которым вы пройдете. При этом необходимо учитывать следующее:

1. Начать движение можно с любого из островов по вашему выбору.
2. Запрещается посещать какой-либо из островов более одного раза.
3. В любой момент вы можете переместиться с острова S, на котором вы находитесь, на другой остров D, который вы еще не посещали. Вы можете попасть с S на D следующим образом:
   
   
   
   1. Пешком: это возможно, если между двумя островами есть мост. В этом случае длина моста добавляется к длине ранее пройденного пути.
   2. Паромом: вы можете воспользоваться этим способом только в том случае, если остров D не достижим c острова S с помощью какой-либо комбинации мостов и/или использованных ранее паромов. При проверке достижимости острова D c острова S следует рассматривать все возможные пути, включая пути, проходящие через острова, на которых вы уже были.
      Обратите внимание, что нет необходимости посещать все острова, и может быть невозможно пройти по всем мостам.

   Напишите программу, которая по заданным N мостам и их длинам вычисляет максимальную длину пути, удовлетворяющего вышеописанным условиям. Длина пути определяется как суммарная длина пройденных мостов.

   2 <= N <= 1 000 000 (N – количество островов в парке)

   1 <= Li <= 100 000 000 (Li – длина i-го моста)

   Входные данные

  Ваша программа должна читать из стандартного ввода следующие данные:

1. Строка 1 содержит целое число N – количество островов в парке. Острова пронумерованы от 1 до N включительно.
2. Каждая из последующих N строк описывает один мост, при этом i-я строка содержит два целых числа, разделенных одним пробелом. Эти два числа описывают мост, построенный от i-го острова. Первое число – это номер острова, до которого строился мост. Второе число – это длина моста Li. Вы можете считать, что концы любого моста находятся на различных островах.

   Выходные данные

   Ваша программа должна вывести в стандартный вывод единственную строку, содержащую одно целое число – максимальную длину пути, который можно пройти.

   Замечание 1. Для некоторых из тестов ответ не может быть вычислен с использованием 32-битного целого типа. Чтобы получить полный балл по этой задаче, вам потребуется использовать тип int64 в языке Паскаль или тип long long в языке C/C++.

   Замечание 2. При запуске программы на языке Паскаль в среде системы тестирования, 64-битные целые типы данных читаются из стандартного потока ввода гораздо медленее, чем 32-битные целые типы данных, даже если читаемые значения помещаются в 32-битный целый тип. Мы рекомендуем вам использовать для чтения данных 32-битный целый тип.