2152: Туристи
Перегляд у форматі PDFГрупа із ~N~ туристів підійшла до переправи на річці. На переправі є човен, який може помістити не більше двох людей. Наближається гроза, і туристам треба якнайшвидше переправитися на той берег річки, де є укриття від дощу.
Відомий час переправи для кожного туриста ~T_i~. Якщо в човні дві людини, то час їх переправи буде дорівнювати більшому часу з двох людей, які знаходяться у човні.
Знайдіть мінімальний час переправи для всієї групи туристів.
Обмеження
- ~3 \le N \le 10^4~
- ~1 \le T_i \le 10^4~
Input
Перший рядок вхідного потоку містить ціле число ~N~ - кількість туристів.
Наступний рядок містить ~N~ цілих чисел ~T_i~ - час переправи для кожного з туристів.
Output
Вивести у вихідний потік одне число - найменший час переправи групи туристів.
Sample Input 1
3
1 10 20
Sample Output 1
31
Sample Input 2
4
1 6 7 8
Sample Output 2
23
Notes
У першому прикладі можливий такий порядок переправи:
- переправляються перший та другий туристи - час рівний 10;
- перший повертається назад - час рівний 1;
- перший та третій переправляються - час рівний 20.
Отже, загальний час, витрачений на переправу, рівний 10 + 1 + 20 = 31.
Коментарі
Чому в 1 прикладі ми не можемо переправити спочатку 1 туриста, а потім 2 і 3 туриста разом і сумарний час вийшов би 1+20=21?
треба човен назад повертати