Adalar

Siz $N$ adadan ibarət bir parkı ziyarət edirsiniz. Hər ada $i$-dən dəqiq bir körpü tikilib. $i$-ci körpünün uzunluğu L_i ilə göstərilir. Parkda cəmi $N$ körpü var. Hər bir körpü iki adanı birləşdirmək üçün tikilmiş olsa da, indi onlar hər iki istiqamətə keçilə bilər. Bundan əlavə, hər iki ada arasında bir unikal bərə işləyir.

Siz bərə əvəzinə körpülərlə getməyi üstün tutursunuz və aşağıdakı qaydalara riayət edərək, keçəcəyiniz körpülərin uzunluqlarının cəmini maksimum etmək istəyirsiniz.

1. Yürüşünüzə istənilən adadan başlaya bilərsiniz.

2. Heç bir adanı bir dəfədən artıq ziyarət etmək olmaz.

3. Hər an olduğunuz ada $S$-dən, hələ ziyarət etmədiyiniz bir ada $D$-yə keçə bilərsiniz. Keçid aşağıdakı qaydada mümkündür:

   1. Piyada: Bu, yalnız aralarında bir körpü varsa mümkündür. Bu halda, körpünün uzunluğu yığılan məsafəyə əlavə edilir.

   2. Bərə: Bunu yalnız $S$-dən $D$-yə körpülər və/və ya daha əvvəl istifadə olunmuş bərələrin istənilən kombinasiyası ilə (hətta artıq ziyarət edilən adalardan keçməklə) getmək mümkün deyilsə, istifadə edə bilərsiniz. Bütün adaları ziyarət etmək məcburi deyil və hər körpüdən keçmək mümkün olmaya bilər.

Verilmiş $N$ körpü və onların uzunluqlarına əsasən, yuxarıdakı qaydalara uyğun olaraq, mümkün olan maksimum piyada məsafəsini hesablaya bilən proqram yazın.