P7176 [COCI 2014/2015 #4] PRIPREME

Ante and Goran are preparing $n$ teams. Each of them has one algorithm that needs to be explained to all teams. Of course, they cannot both explain to the same team at the same time, and neither of them can explain to multiple teams at the same time. Given the time needed to explain to each team, determine the minimum total time required.

The first line contains an integer $n$, the number of teams. The next line contains $n$ space-separated integers $a_i$, where $a_i$ is the time needed to explain to team $i$.

Output a single line: the minimum total time required.

#### Explanation for Sample 1 Each team needs $2$ units of time to understand and implement an algorithm. The following is one feasible teaching plan. | Ante | Goran | Time | | :----------: | :----------: | :----------: | | Team 1 | Team 2 | $2$ | | Team 2 | Team 3 | $2$ | | Team 3 | Team 1 | $2$ | | All finished | All finished | $6$ | #### Explanation for Sample 2 One optimal schedule is that Ante teaches teams $2, 3, {\color{red}x}, 1$ in order, but there is a $1$ unit time pause at $\color{red}x$. Goran will teach teams $1, 3, 2$ in order. #### Constraints - For $40\%$ of the testdata, $1 \le n \le 7$. - For $100\%$ of the testdata, $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](https://hsin.hr/coci/archive/2014_2015/contest4_tasks.pdf) _T3 PRIPREME_.** Translated by ChatGPT 5