\includegraphics{https://static.e-olymp.com/content/8e/8e76e21e23f0b735c19f0a5c00759fdbba7280ba.jpg} Siz \textbf{N }adası olan parka gəlmişsiniz. Hər bir \textbf{i-}ci adadan digər adaya nə vaxt isə bir körpü tikilmişdir. Bu körpünün uzunluğu\textbf{ Li }ilə işarə olunur. Parkda cəmi \textbf{N} körpü var. Baxmayaraq ki, bütün körpülər bir adadan digərinə doğru tikilmişdi, indiki zamanda hər bir körpüdən ixtiyari iki istiqamətdə hərəkət etmək olar. Bundan başqa, hər bir iki ada arasında bərə vasitəsilə oraya və əks istiqamətdə getmək olar. Sizə bərə vasitəsilə getməkdənsə, körpü ilə getmək daha çox xoş gəldiyindən Siz istəyirsiniz ki, getdiyiniz yolda körpülərin uzunluqları cəmini maksimum etmək istəyirsiniz. Bu zaman aşağıdakıları nəzərə almaq lazımdır: \begin{enumerate} \item Sizin seçməyinizə görə istənilən adadan hərəkətə başlamaq olar. \item Hər hansı adaya bir dəfədən artıq getmək qadağandır. \item İstənilən anda Siz olduğunuz\textbf{ S} adasından hələ getmədiyiniz digər \textbf{D} adasına keçə bilərsiniz. Sizə \textbf{S}-dən \textbf{D}-yə aşağıdakı kimi düşmək olar: \begin{enumerate} \item Piyada: iki ada arasında körpü varsa, bu mümkündür. Bu halda əvvəl gedilən yolun uzunluğunun üzərinə körpülərin uzunluqları da əlavə olunur. \item Bərə ilə: Siz bu üsuldan yalnız hər hansı körpülər kombinasiyasından və ya əvvəllər istifadə edilmiş bərənin köməyi ilə \textbf{S} adasından \textbf{D }adasına keçmək mümkün olmadıqda istifadə etmək olar. \textbf{S} adasından \textbf{D} adasına getməyin mümkünlüyünün yoxlanmasında bütün mümkün yollara, Sizin artıq olduğunuz adalardan keçən yollar da daxil olmaqla baxılmalıdır. Diqqət yetirin ki, bütün adalara baş çəkmək zəruri deyil və ola bilər ki, bütün körpülərdən keçmək mümkün olmasın. \end{enumerate} \end{enumerate} Verilmiş \textbf{N }körpü və onların uzunluğuna görə yuxarıdakı şərtləri ödəyən yolun maksimum uzunluğunu hesablayan proqramı yazın. Yolun uzunluğu bütün keçilmiş körpülərin cəmi uzunluğu kimi müəyyənləşir \textbf{2} <= \textbf{N} <= \textbf{1 000 000} (\textbf{N} --parkdakı adaların sayıdır) \textbf{1} <= \textbf{Li} <= \textbf{100 000 000} (\textbf{Li} -- \textbf{i}-ci körpünün uzunluğudur) \InputFile Sizin proqram standart girişdən aşağıdakı verilənləri oxumalıdır: \begin{enumerate} \item Birinci sətirdə parkdakı adaların sayı olan tam \textbf{N} ədədi yerləşir. Adalar \textbf{1}-dən \textbf{N} də daxil olmaqla \textbf{N}-dək nömrələnmişdir. \item Hər bir sonrakı \textbf{N} sayda sətrin hər birində bir körpü təsvir edilir. Bu zaman \textbf{i}-si sətirdə boşluq işarəsi ilə ayrılmış iki tam ədəd yerləşir. Bu iki ədəd \textbf{i}-ci adada tikilmiş körpünü təsvir edir. Birinci ədəd körpü tikilməmişdən əvvəl adanın nömrəsidir. İkinci ədəd körpünün \textbf{Li} uzunluğudur. Siz hesab edə bilərsiniz ki, istənilən körpünün ucları müxtəlif adalarda yerləşir. \end{enumerate} \OutputFile Sizin proqram standart çıxışa keçmək mümkün olan yolun maksimum uzunluğu olan bir tam ədəd yerləşən yeganə sətir verməlidir. \textbf{Qeyd 1.} Testlərdən bəziləri üçün cavab \textbf{32}-bitlik tam tipdən istifadə etməklə hesablanmaya bilər. Bu məsələ üzrə tam xal almaq üçün sizdən Paskal dilində\textbf{ int64} tipindən və ya C/C++ dilində \textbf{long long} tipindən istifadə etmək tələb olunur. \textbf{Qeyd 2.} Testləşdirmə sistemi mühitində Paskal dilində proqramın işə salınmasında \textbf{64}-bitlik tam tip verilənlər standart giriş axınından \textbf{32}-bitlik tam tip verilənlərə nisbətən həddindən artıq gec oxunur, hətta əgər oxunan qiymətlər \textbf{32}-bitlik tam tipdə yerləşdirilsə belə. Biz verilənlərin oxunması üçün \textbf{32}-bitlik tam tipdən istifadə edilməsini tövsiyə edirik.