\includegraphics{https://static.e-olymp.com/content/8e/8e76e21e23f0b735c19f0a5c00759fdbba7280ba.jpg} Вы приехали в парк, в котором \textbf{n }островов. От каждого из островов \textbf{i }когда-то построили один мост до какого-то другого острова. Длина такого моста обозначается \textbf{L_i}. Всего в парке \textbf{n }мостов. Хотя все мосты строили от одного острова до другого, в настоящее время по каждому мосту можно двигаться в любом из двух направлений. Помимо этого, между каждыми двумя островами ходит один паром как туда, так и обратно. Так как вам больше нравится ходить по мостам, чем ездить на пароме, вы хотите максимизировать суммарную длину мостов, по которым вы пройдете. При этом необходимо учитывать следующее: \begin{enumerate} \item Начать движение можно с любого из островов по вашему выбору. \item Запрещается посещать какой-либо из островов более одного раза. \item В любой момент вы можете переместиться с острова \textbf{s}, на котором вы находитесь, на другой остров \textbf{d}, который вы еще не посещали. Вы можете попасть с \textbf{s} на \textbf{d} следующим образом: \begin{enumerate} \item Пешком: это возможно, если между двумя островами есть мост. В этом случае длина моста добавляется к длине ранее пройденного пути. \item Паромом: вы можете воспользоваться этим способом только в том случае, если остров \textbf{d} не достижим c острова \textbf{s} с помощью какой-либо комбинации мостов и/или использованных ранее паромов. При проверке достижимости острова \textbf{d} c острова \textbf{s} следует рассматривать все возможные пути, включая пути, проходящие через острова, на которых вы уже были. Обратите внимание, что нет необходимости посещать все острова, и может быть невозможно пройти по всем мостам. \end{enumerate} \end{enumerate} Напишите программу, которая по заданным \textbf{n }мостам и их длинам вычисляет максимальную длину пути, удовлетворяющего вышеописанным условиям. Длина пути определяется как суммарная длина пройденных мостов. \InputFile Первая строка содержит количество островов \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^6}) в парке. Острова пронумерованы от \textbf{1 }до \textbf{n }включительно. Каждая из последующих \textbf{n }строк описывает один мост, при этом \textbf{i}-я строка содержит два целых числа, разделенных одним пробелом. Эти два числа описывают мост, построенный от \textbf{i}-го острова. Первое число - это номер острова, до которого строился мост. Второе число - это длина моста \textbf{L_i} (\textbf{1} ≤ \textbf{L_i} ≤ \textbf{10^8}). Вы можете считать, что концы любого моста находятся на различных островах. \OutputFile Вывести одно целое число -- максимальную длину пути, который можно пройти. \textbf{Замечание 1.} Для некоторых из тестов ответ не может быть вычислен с использованием \textbf{32}-битного целого типа. Чтобы получить полный балл по этой задаче, вам потребуется использовать тип \textbf{int64} в языке Паскаль или тип \textbf{long long} в языке C/C++. \textbf{Замечание 2.} При запуске программы на языке Паскаль в среде системы тестирования, \textbf{64}-битные целые типы данных читаются из стандартного потока ввода гораздо медленее, чем \textbf{32}-битные целые типы данных, даже если читаемые значения помещаются в \textbf{32}-битный целый тип. Мы рекомендуем вам использовать для чтения данных \textbf{32}-битный целый тип.