# Problem F

Take a break!

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.

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 |