Рада и Нада се две баби - јатрви. Тие живеат во соседни куќи, секогаш спремаат ист ручек и вечера, заедно одат на пазар да пазарат намирници и купуваат од истите намирници. На пазарот постојат N тезги кои ги посетуваат и двете баби. За секоја тезга се знае колку време ќе биде потребно за услужување на некој муштерија откако тој ќе дојде на ред (на некоја тезга се продаваат домати, на некоја ориз… па така за секоја времето може да е различно од другите).

И денес баба Рада и баба Нада пристигнале заедно на пазарот. Но, ако тргнат заедно да одат од тезга на тезга, цело време едната ќе треба да ја чека другата да заврши. Затоа, тие решиле да направат распоред на посетување на тезгите во меѓусебно различен редослед, за да завршат најбрзо што може.

Претпоставете дека дури бабиве се на пазарот, нема други муштерии освен нив двете. Пресметајте колку најмалку време им е потребно и двете да ги посетат сите тезги и да ги купат потребните намирници, ако знаете по колку време се троши за купување на секоја од тезгите. Времето за префрлање од тезга на тезга земете дека е нула.

Влез

Во првиот ред има цел број N, бројот на тезгите (1≤N≤300 000).
Во вториот ред има N цели броеви одделени со по едно празно место, при што i-тиот број го претставува времето (во минути) кое се троши на i-тата тезга да се заврши со купување. Сите броеви во влезот ќе бидат во интервалот [1, 300 000]

Бодување: Кај тест случаи кои носат 40% од поените важи дека N≤7.

Излез

Во првиот ред отпечатете го бараното време (во минути).

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
3
2 2 2

излез
6

влез
3
4 2 1

излез
8

Објаснување за првиот пример: На секоја тезга еден муштерија троши по 2 минути за да го спроведе купувањето. Еден можен распоред е ако баба Рада ги посети по ред тезгата 1, тезгата 2 и тезгата 3, а баба Нада прво отиде на тезгата 3, потоа на тезгата 1 и на крај на тезгата 2. Така тие две паралелно ќе завршат работа и ќе бидат потребни вкупно 2+2+2=6 минути за тоа.

Објаснување за вториот пример: Еден можен оптимален распоред е баба Рада да ги посети по ред тезгите 2, 3 и 1, а баба Нада да ги посети по ред тезгите 1, 3 и 2. Притоа, да забележиме дека откако баба Рада ќе ја посети тезгата 3, ќе почека 1 минута за да ја посети тезгата 1 затоа што во првите 4 минути на првата тезга е баба Нада. Со овој распоред, за да заврши со пазарење, на баба Рада ќе и бидат потребни 2+1+1(чека)+4=8, a на баба Нада 4+1+2=7 минути. Сепак, на крај, двете може заедно да си заминат после 8 минути.