Optimal Book Pile Merging

You are given n books. Initially, each book forms a pile by itself with a given weight and a wear value of 0. You want to merge all these piles into one pile. In each merge, you can put one pile on top of another pile, and the two piles become one.

If you put pile i on top of pile j, the energy cost of this merge is computed as follows:

\(\text{Cost} = W_i + (R_i + R_j)\)

where:

• \(W_i\) is the weight of the pile that is moved (pile i).
• \(R_i\) and \(R_j\) are the wear values of piles i and j, respectively.

After merging two piles with parameters \((W_1, R_1)\) and \((W_2, R_2)\), you can choose which pile to put on top. It is always optimal to put the pile with the smaller weight on top since the merge cost depends on the top pile's weight. Thus, if \(W_1 \le W_2\), then the merge cost is

\(W_1 + (R_1+R_2)\)

and the newly formed pile will have:

• Weight: \(W_1+W_2\)
• Wear value: \(2R_2+1\)

If \(W_1 > W_2\), then the merge cost is

\(W_2 + (R_1+R_2)\)

and the new pile will have:

• Weight: \(W_1+W_2\)
• Wear value: \(2R_1+1\)

Your task is to determine the sequence of merges that minimizes the total energy cost to merge all books into a single pile and output this minimum cost.

inputFormat

The first line of input contains a single integer \(n\) (the number of books). The second line contains \(n\) space-separated positive integers representing the weights of the books.

outputFormat

Output a single integer representing the minimum total energy cost required to merge all the piles into one pile.

sample

2
3 100

3