题目描述
Problem Description
Ante and Goran are preparing for $n$ teams. Each of them has an algorithm to explain to all the teams.
Naturally, they cannot explain to the same team simultaneously, nor can they explain to multiple teams at once.
Given the time required to explain to each team, you need to determine the minimum time required for the explanations.
Input Format
The first line of input contains the integer $n$, the number of teams.
The next line contains $n$ space-separated integers $a_i$, representing the time required to explain to the $i$-th team.
Output Format
Output a single line, the minimum time required for the explanations.
Sample Input and Output
Sample Input #1
3
2 2 2
Sample Output #1
6
Sample Input #2
3
4 1 2
Sample Output #2
8
Sample Input #3
4
1 3 2 1
Sample Output #3
7
Notes
Sample 1 Explanation
Each team requires $2$ units of time to understand and implement an algorithm. Here is one feasible method of teaching:
| Ante | Goran | Time |
|---|---|---|
| Team 1 | Team 2 | $2$ |
| Team 2 | Team 3 | $2$ |
| Team 3 | Team 1 | $2$ |
| All done | All done | $6$ |
Sample 2 Explanation
One optimal time arrangement is for Ante to explain to teams $2, 3, {\color{red}x}, 1$ in sequence, with a $1$ unit time pause at $\color{red}x$. Goran will explain to teams $1, 3, 2$ in sequence.
Data Size and Constraints
- For $40\%$ of the data, $1 \le n \le 7$.
- For $100\%$ of the data, $1 \le n \le 3 \times 10^5$.
For all valid $a_i$, $a_i \in [1, 3 \times 10^5]$.
Notes
This problem is translated from COCI2014-2015 CONTEST #4 T3 PRIPREME.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分