Dubious Delivery


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 640M

Authors:
Problem type
Allowed languages
Assembly, C, C++, Java, Kotlin, Pascal, Perl, Python, Scratch, Text

The AI bubble has finally burst. Now that this has happened, Catherine has been designated a crucial humanitarian mission of the utmost moral importance. Catherine must deliver all the unused graphics cards from an abandoned data centre to the poor, desperate gamers of the world, saving them from a cruel time when they couldn't play the newest video games in the highest resolution.

The graphics cards are stored in a row of \(n\) server racks. Each server rack has an associated weight. To prepare all \(n\) server racks for delivery, Catherine must form a single tower of all \(n\) server racks stacked on top of each other, with the help of a robot.

In each step, this robot can merge two adjacent towers of server racks (including individual server racks), creating one new tower with the combined weight of the two.

This is repeated for \(n - 1\) turns, after which all server racks will be part of a single tower.

For instance, here is a chart depicting all possible sequences of steps to construct a single tower from \(3\) adjacent server racks with weights \(1\), \(2\), and \(3\):

Figure One

Notice how there are three towers, then two towers, then one tower.

Combining towers costs the robot energy. Unfortunately, vibe coding has completely taken away Catherine's ability to code, and without it, she has made a blunder. To merge two towers, rather than picking up the lightest tower and placing it on top, the robot will pick up the heaviest tower and place it on top.

This means that each turn, the robot incurs some energy cost; and that cost is the total weight of the heaviest of the two towers being merged in that step.

Given \(n\) server racks of specified weights, what is the least expensive order for them to be combined in?

Input

The input consists of two lines.

The first line contains an integer \(3 \leq n \leq 5\times 10^2\), representing the amount of server racks in the row.

The second line contains \(n\) integers, \(1 \leq w_i \leq 1000\), representing the weight of the \(i\)th server.

Output

The program must output the total cost of the most optimal strategy for the robot to combine the server racks into a single tower.

Examples

Example 1

Input:

3
1 2 3

Output:

5

In the figure above, it can be seen that there are two sequences to stack three server racks. The best sequence is the following:

  • In the first step, rack \(1\) (\(w_1 = 1\)) can be combined with rack \(2\) (\(w_2 = 2\)), costing \(2\) units of energy
  • In the secnd step, racks \(1\) and \(2\) can be combined with rack \(3\), costing \(3\) units of energy

This sequence is depicted below:

Figure Two

Example 2

Input:

4
1 2 5 3

Output:

15

There is more than one sequence that achieves the optimal cost of \(15\). One of them is the following:

  • In the first step, rack \(1\) (\(w_1 = 1\)) can be combined with rack \(2\) (\(w_2 = 2\)), costing \(2\) units of energy
  • In the second step, racks \(1\) and \(2\) can be combined with rack \(3\) (\(w_3 = 5\)), costing \(5\) units of energy
  • In the third step, racks \(1\), \(2\), and \(3\) can be combined with rack \(4\) (\(w_4 = 3\)), costing \(8\) units of energy

This sequence is depicted below:

Figure Three


Comments

There are no comments at the moment.