Недавно Вася разрабатывал новый алгоритм по оптимизации приема клиентского потока и рассматривал следующую задачу.

Пусть в очереди к кассе стоят n человек, причем, каждый характеризуется положительным целым числом a_i — временем обработки этого клиента. Особенность же данной конкретной кассы в том, что она способна принять двух клиентов одновременно, причем время обработки двух клиентов со временами a_i и a_j равно max(a_i, a_j). Обратите внимание, что обработка — это непрерываемый процесс, и поэтому, если два человека одновременно обслуживаются в кассе, то это значит, что они одновременно начали обрабатываться, и одновременно закончат (возможно, что одному из них придется подождать).

Вася в своем алгоритме использовал гениальную эвристику — пока в очереди больше одного человека на обработку посылаются одновременно какие-то два человека из первых трех, стоящих в начале очереди. В случае, если в очереди остается единственный клиент номер i, то он проходит в кассу, и его обслуживание занимает a_i времени. Заметим, что общее количество фаз обработки будет всегда равно ⌈n / 2⌉ (операция ⌈x⌉ означает округление вверх до ближайшего целого числа).

Вася считает, что этот метод поможет справиться со столь ненавистными всем очередями, и поэтому попросил Вас разработать программу, которая определит минимальное время, за которое обработается вся очередь с помощью этого алгоритма.