Problem F
Take a break!

Young Woman Resting in a Music Room, Alfred Stevens, 1932.

Some call you lazy, others (yourself included) call you a break optimizer.

You have been tasked with a large number of chores around your house. The tasks vary greatly in difficulty—some literally only take a second, like putting a fork the dishwasher; others require a lot more effort, like cleaning the drain.

Each task has a difficulty, which is the number of seconds it takes you to complete the task when you are fully rested. Whenever you complete a task and directly start another, its completion time doubles. Formally, completing a task with difficulty $d$ after $i$ tasks before it, without any intervening breaks, takes $ d \cdot 2^ i $ seconds.

However, whenever you take a solid break of at least one hour, you become fully rested. (Shorter breaks don’t do anything for you.)

For instance, here are two (suboptimal) ways of scheduling the four tasks in sample $3$:

In both schedules, task 3 takes $2^2\cdot 1000=4000$ seconds.

You have to complete all tasks, in any order. You begin fully rested. What is the shortest time to complete all tasks, including breaks?

Input

The first line contains the number $1 \leq n \leq 100\, 000$ of tasks to complete. The second line consists of $n$ integers $d_1, \ldots , d_ n$, the difficulty of each task in seconds, where $1 \leq d_ i \leq 28\, 800$.

There are three different test groups.

Output

Output a single integer, the minimal time in seconds it takes for you to complete all tasks, including your breaks.

2
300 400

1000

3
1000 1100 1000

7100

4
1000 1100 1000 800

9300

12
1 1 1 1 1 1 1 1 1 1 1 1

3726

13
1 1 1 1 1 1 1 1 1 1 1 1 1

3790