Во время выполнения задания разведгруппа проходит
через минные заграждения противника. В связи с требованием скрытности
проведения операции мины в заграждении решено не снимать, а поскольку
миноискатель у группы один, то перемещаться необходимо следующим образом — в
сторону противника переходят парой, затем один человек возвращается, чтобы
принести оставшейся группе миноискатель.
Каждый человек переходит минные заграждения со своей
скоростью. Скорость пары определяется скоростью более медленного её члена.
Рассчитайте минимальное время, требующееся группе из N человек на
пересечение заграждения.
Первая строка входного файла содержит число N
— количество человек в группе (2 ≤ N ≤ 100). Следующие N строк
задают время, необходимое на преодоление минного заграждения для каждого члена
группы (время от 1 до 600 секунд, количество секунд целое).
Выведите в первой строке выходного файла одно число —
минимальное суммарное время, которое потребуется группе для пересечения
заграждения.
Пример
|
Поток ввода
|
Поток вывода
|
|
4
1
10
5
2
|
17
|
