Vasya has recently developed a new algorithm to optimize the reception of customer flow and he considered the following problem.

Let the queue to the cashier contain n people, at that each of them is characterized by a positive integer a_i — that is the time needed to work with this customer. What is special about this very cashier is that it can serve two customers simultaneously. However, if two customers need a_i and a_j of time to be served, the time needed to work with both of them customers is equal to max(a_i, a_j). Please note that working with customers is an uninterruptable process, and therefore, if two people simultaneously come to the cashier, it means that they begin to be served simultaneously, and will both finish simultaneously (it is possible that one of them will have to wait).

Vasya used in his algorithm an ingenious heuristic — as long as the queue has more than one person waiting, then some two people of the first three standing in front of the queue are sent simultaneously. If the queue has only one customer number i, then he goes to the cashier, and is served within a_i of time. Note that the total number of phases of serving a customer will always be equal to ⌈n / 2⌉.

Vasya thinks that this method will help to cope with the queues we all hate. That's why he asked you to work out a program that will determine the minimum time during which the whole queue will be served using this algorithm.