Група људи током ноћи стоји на једној обали реке. Имају само једну светиљку. Преко реке је разапет мост преко ког истовремено могу да пређу највише две особе и то само ако носе светиљку. За сваку особу је познато време потребно за прелазак моста. Ако две особе прелазе мост заједно, крећу се брзином спорије особе. Напиши програм који одређује најмање време потребно да сви људи из групе пређу на другу обалу реке.

Улаз

Са стандардног улаза се учитава број особа \(n\) (\(1 \leq n \leq 100\)), а затим, у \(n\) наредних редова времена потребна да тих \(n\) особа пређе мост.

Излаз

На стандардни излаз исписати најмање време потребно да сви пређу на другу обалу.

Пример

Улаз

4
1
2
5
10

Излаз

17

Објашњење

Прво прелазе особа 1 и 2 и враћа се особа 1 (за то им је потребно \(\max{(1, 2)} + 1 = 3\) минуте). Након тога заједно прелазе особа 3 и 4 и враћа се особа 2 (за то им је потребно \(\max{(5, 10)} + 2 = 12\) минута). Након тога заједно прелазе особа 1 и 2 (за то им је потребно \(\max{(1, 2)} = 2\) минуте). Укупно је, дакле, потребно \(3 + 12 + 2 = 17\) минута.