Hide

Problem F
Take a break!

/problems/lthchallenge22.takeabreak/file/statement/en/img-0001.jpg
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$:

\includegraphics[width=.8\textwidth ]{img/sample-3.pdf}

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.

Group

Points

Additional constraints

1

$25$

$n\leq 1\, 000$

2

$10$

$d_1=\cdots = d_ n$

3

$65$

none

Output

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

Sample Input 1 Sample Output 1
2
300 400
1000
Sample Input 2 Sample Output 2
3
1000 1100 1000
7100
Sample Input 3 Sample Output 3
4
1000 1100 1000 800
9300
Sample Input 4 Sample Output 4
12
1 1 1 1 1 1 1 1 1 1 1 1
3726
Sample Input 5 Sample Output 5
13
1 1 1 1 1 1 1 1 1 1 1 1 1
3790

Please log in to submit a solution to this problem

Log in