Під час виконання завдання розвідгрупа проходить через мінні загородження супротивника. У зв'язку з вимогами секртності проведення операції міни у загородженні вирішено не знімати, але оскільки міношукач у групі один, то переміщуватись потрібно наступним чином — у сторону супротивника переходять парою, потім одна людина повертається, щоб принести групі, що залишилась, міношукач.

Кожна людина переходить мінні загородження зі своєю швидкістю. Швидкість пари визначається швидкістю більш повільного її члена.

Розрахуйте мінімальний час, який потрібно групі з N чоловік на подолання загородження.

Вхідні данні

Перший рядок вхідного файлу містить число N — кількість людей у групі (2 ≤ N ≤ 100). Наступні N рядків задають час, необхідний дял подолання мінного загородження для кожного члена групи (час від 1 до 600 секунд, кількість секунд ціла).

Вихідні данні

Виведіть у першому рядку вихідного файлу одне число — мінімальний сумарний час, який потрібно групі для подолання загородження.