Adalar

Siz N adası olan parka gəlmişsiniz. Hər bir i-ci adadan digər adaya nə vaxt isə bir körpü tikilmişdir. Bu körpünün uzunluğu Li ilə işarə olunur. Parkda cəmi 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:

1. Sizin seçməyinizə görə istənilən adadan hərəkətə başlamaq olar.

2. Hər hansı adaya bir dəfədən artıq getmək qadağandır.

3. İstənilən anda Siz olduğunuz S adasından hələ getmədiyiniz digər D adasına keçə bilərsiniz. Sizə S-dən D-yə aşağıdakı kimi düşmək olar:

   1. 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.

   2. 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ə S adasından D adasına keçmək mümkün olmadıqda istifadə etmək olar. S adasından 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.

Verilmiş 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

2 <= N <= 1 000 000 (N –parkdakı adaların sayıdır)

1 <= Li <= 100 000 000 (Li – i-ci körpünün uzunluğudur)

Giriş verilənləri

Sizin proqram standart girişdən aşağıdakı verilənləri oxumalıdır:

1. Birinci sətirdə parkdakı adaların sayı olan tam N ədədi yerləşir. Adalar 1-dən N də daxil olmaqla N-dək nömrələnmişdir.

2. Hər bir sonrakı N sayda sətrin hər birində bir körpü təsvir edilir. Bu zaman i-si sətirdə boşluq işarəsi ilə ayrılmış iki tam ədəd yerləşir. Bu iki ədəd 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 Li uzunluğudur. Siz hesab edə bilərsiniz ki, istənilən körpünün ucları müxtəlif adalarda yerləşir.

Çıxış verilənləri

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.

Qeyd 1. Testlərdən bəziləri üçün cavab 32-bitlik tam tipdən istifadə etməklə hesablanmaya bilər. Bu məsələ üzrə tam xal almaq üçün sizdən Paskal dilində int64 tipindən və ya C/C++ dilində long long tipindən istifadə etmək tələb olunur.

Qeyd 2. Testləşdirmə sistemi mühitində Paskal dilində proqramın işə salınmasında 64-bitlik tam tip verilənlər standart giriş axınından 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 32-bitlik tam tipdə yerləşdirilsə belə. Biz verilənlərin oxunması üçün 32-bitlik tam tipdən istifadə edilməsini tövsiyə edirik.

Nümunələr