Група iз \(N\) туристiв пiдiйшла до переправи на рiчцi. На переправi є човен, який може помiстити не бiльше двох людей. Наближається гроза, i туристам треба якнайшвидше переправитися на той

берег рiчки, де є укриття вiд дощу. Вiдомий час переправи для кожного туриста \(T_i\). Якщо в човнi двi людини, то час їх переправи буде дорiвнювати бiльшому часу з двох людей,

якi знаходяться у човнi. Знайдiть мiнiмальний час переправи для всiєї групи туристiв.

Обмеження:

• \(3 \le N \le 10^4\)
• \(1 \le T_i \le 10^4\)

Формат вхiдних даних:

Перший рядок вхiдного потоку мiстить цiле число \(N\) - кiлькiсть туристiв. Наступний рядок мiстить \(N\) цiлих чисел \(T_i\) час переправи для кожного з туристiв.

Формат вихiдних даних:

Вивести у вихiдний потiк одне число - найменший час переправи групи туристiв.

Приклади:

Входові дані 1:

3
1 10 20

Виходові дані 1:

31

Входові дані 2:

4
1 6 7 8

Виходові дані 2:

23

Пояснення:

У першому прикладi можливий такий порядок переправи:

• переправляються перший та другий туристи - час рiвний 10;
• перший повертається назад - час рiвний 1;
• перший та третiй переправляються - час рiвний 20. Отже, загальний час, витрачений на переправу, рiвний 10 + 1 + 20 = 31