Splitting DNA

You are studying a protein that splits long chains of DNA into smaller chains. The protein works as follows. To split a long chain of DNA, the protein first "reads" the whole chain and cuts it into two parts (not necessarily equal), then recursively splits the two smaller chains.

Splitting a chain $S_1S_2$ into the two parts $S_1$ and $S_2$ takes an amount of energy proportional to the length of $S_1S_2$ (the sum of the lengths of $S_1$ and $S_2$). More generally, splitting a chain $S_1 \ldots S_N$ ($N > 1$) takes an energy proportional to the length of $S_1 \ldots S_N$ to cut it into two, plus the energy required to recursively split the two smaller chains.

You know the original DNA chain $S_1 \ldots S_N$ and the $N$ fragments $S_1, \ldots, S_N$ obtained after the split. Since nature is usually very energy-efficient, you wonder what the minimal energy required to split the DNA chain is.

You noticed that the computation of this minimal energy only depends on $L_1, \ldots, L_N$, where $L_i$ is the length of $S_i$. Given these $N$ integers $L_1, \ldots, L_N$, you want to compute the minimal energy required by the protein to split the long chain into these chunks.

The input consists of two lines:

• the first line contains the number $N$ of strings, an integer;
• the second line contains $N$ space-separated integers representing $L_1, \ldots, L_N$.

Print a single line with a single integer: the minimal total energy required to split the original chain.

• $1 \le N \le 500$;
• $0 \le L_i \le 10^{14}$ for all $1 \le i \le N$.