Учасників полярної експедиції, які зимували на крижині, спіткало велике лихо: крижина розкололася, і всі вони опинилися на маленькому її уламку. Потрібно було якнайшвидше переправитися через широку тріщину. У їх розпорядженні є один двомісний надувний човен. Для кожного полярника відомий час, за який він може переправитися на цьому човні через тріщину. Якщо ж у човні перебувають 2 полярники, час переправи дорівнює часу неповороткішого з них (тобто того з цих двох, хто потребує більше часу). За який мінімальний час всі полярники можуть переправитися на велику крижину?

Вхідні дані

Програма зчитує у першому рядку натуральне число ~N~ (~3\leqslant N\leqslant 1000~) – кількість полярників, а у другому рядку через пропуски – ~N~ натуральних чисел, не більших 10000, які задають час переправи кожного полярника.

Результати

Програма виводить одне число – шукану мінімальну тривалість переправи.

Приклади

Вхід

4
1 6 7 8

Результат

23

Вхід

4
300 500 800 1000

Результат

2800

Примітка

Тут треба грамотно скомбінувати дві жадібні стратегії. Перший тест з умови розв'язується однією з них, другий – іншою з них, кожен з решти тестів – або однією з цих самих двох стратегій, або грамотною комбінацією обох цих жадібних стратегій.