Програмчлалын олимпиадын бодлогын архив

Та N арал бүхий цэцэрлэгээр аялах гэж байгаа. i-р арал бүрээс яг нэг гүүр барьжээ.
Энэ гүүрний уртыг L_i гэж тэмдэглэнэ.
Цэцэрлэгт байгаа нийт гүүрний тоо N.
Гүүр бүрийг нэг арлаас эхлэн өөр нэг арал руу чиглүүлэн барьсан боловч одоо бол аль ч чиглэлд явж болно.
Мөн хос арал бүрийн хувьд тэдгээрийн хооронд нааш цааш сэлж чадах нэг завь байгаа.
Та явган явахыг завиар сэлснээс илүүд үздэг тул доорх хязгаарлалтуудыг хангаж байх үед, туулсан гүүрнүүдийн нийт уртыг хамгийн их байлгахыг хүсч байгаа:
• Та аяллаа ямар ч арал дээрээс эхэлж болно.
• Ямар ч арал дээр нэгээс олон удаа очиж болохгүй.
• Та одоо байгаа арал S – ээсээ өмнө нь очоогүй байгаа D арал руу шилжих боломжтой.
S – ээс D рүү дараах хоёр аргын нэгээр шилжиж болно:
o Алхах: Уг хоёр арлын хооронд гүүр байгаа тохиолдолд л боломжтой.
Энэ үед таны алхсан нийт зай гүүрний уртаар нэмэгдэнэ, эсвэл
o Завиар сэлэх: Энэ аргыг зөвхөн S арлаас D арал руу гүүрүүд ба/эсвэл өмнө нь хэрэглэсэн завиудын ямар ч хослолыг ашиглан хүрч болохгүй тохиолдолд хэрэглэнэ.
(Хүрч болох эсэхийг шалгах үед бүх замыг авч үзэх ба өмнө нь очсон арлуудыг дайрсан замуудыг ч авч үзнэ.)
Бүх арал дээр очих албагүй ба бүх гүүрийг туулах боломжгүй байж болохыг анхаар.
ДААЛГАВАР
N ширхэг гүүр уртуудынхаа хамт өгөгдсөн үед дээрх дүрмийг баримтлан гүүрэн дээгүүр алхах замын нийт уртын хамгийн их утгыг олох програм бич.
ХЯЗГААРЛАЛТУУД
2 <= N <= 1,000,000 Цэцэрлэг дэх гүүрүүдийн тоо.
1<= L_i <= 100,000,000 i гүүрийн урт.

Input

Таны програм стандарт оролтоос дараах өгөгдлийг унших ёстой:
• Нэгдүгээр мөрөнд цэцэрлэг дэх гүүрүүдийн тоо болох N бүхэл тоо байрлана.
Арлуудыг 1 – ээс багагүй N – ээс ихгүй байх тоонуудаар дугаарлана.
• Дараагийн N ширхэг мөр бүрт нэг гүүрийг тодорхойлно.
i-р мөрөнд i арлаас эхэлж баригдсан арлыг зайгаар тусгаарлагдсан хоёр бүхэл тоогоор тодорхойлсон байгаа.
Эхний бүхэл тоо нь гүүрийн нөгөө талд байгаа арлыг илэрхийлэх ба хоёр дахь бүхэл тоо нь гүүрийн урт L_i – г харуулна.
Гүүр бүрийн хувьд хоёр төгсгөл нь ялгаатай арлууд дээр байна гэж тооцож болно.

Output

Таны програм стандарт гаралт руу алхсан замын уртын хамгийн их утга болох ганц бүхэл тоо агуулсан нэг мөрийг хэвлэх ёстой.
ТАЙЛБАР 1: Зарим тестийн хувьд хариу нь 32-битийн бүхэл тоонд багтахгүй байх тул энэ бодлогонд бүтэн оноо авахын тулд Паскалийн int64 эсвэл
C/C++ - ийн long long төрлийг хэрэглэх хэрэгтэй.

Example

Input:
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3


Output:
24



N=7 үед жишээн дэх гүүрүүд нь (1-3), (2-7), (3-4), (4-1), (5-1), (6-3) болон (7-2) байна. 
2 болон 7 арлуудыг холбосон хоёр гүүр байгааг анхаарна уу. 

Хамгийн хол зайг алхах нэг замыг доор үзүүлэв: 

o	5 арлаас аяллаа эхэлнэ. 

o	9 урттай гүүрийг туулж 1 аралд хүрнэ. 

o	8 урттай гүүрийг туулж 3 аралд хүрнэ. 

o	4 урттай гүүрийг туулж 6 аралд хүрнэ. 

o	6 арлаас 7 арал руу завиар сэлж хүрнэ. 

o	3 урттай гүүрийг туулж 2 аралд хүрнэ. 


Ингэсний эцэст та 2 аралд хүрэх ба нийт алхсан замын урт нь 9+8+4+3 = 24 болно. 

Огт очоогүй ганц арал нь 4 арал байна. 
Дээр үзүүлсэн аяллын эцэст та 4 аралд хүрч чадахгүй юм. Учир нь: 

o	2 арлыг (таны одоо байгаа арал) 4 аралтай холбосон гүүр байхгүй байгаа тул та алхаж очиж чадахгүй. 

o	4 арал руу таны одоо байгаа 2 арлаас хүрэх боломжтой тул та завиар сэлж очиж чадахгүй. 
Уг аралд хүрэх нэг арга нь: (2-7) гүүрийг туулж, дараа нь 7 арлаас 6 арал хүрэхэд хэрэглэсэн завиа дахин хэрэглээд, 
(6-3) болон (3-4) гүүрүүдийг туулах. 


Тайлбар: Интернетийн хурд хүрэхгүй байгаагаас албан ёсны бүх тестийг оруулж чадсангүй. Иймд бүх тестээр 
шалгуулъя гэвэл энд дарж англи хувилбараас бодолтоо илгээнэ үү.