Card Fusion Event

Time limit1sMemory limit512 MB

Summary

Merge adjacent cards until one remains, where a merge pays the sum of both levels and keeps only the left card's level; maximize total gold.

Level: Medium6 of 10
Topics: Intervals, Dynamic programming
Solved: No attempts yet

Problem

Yeonggwan joined the card fusion event of a mobile board game.

The event puts $n$ cards in a row in a fixed order, and each card carries one level.

You may append card B to card A to merge them into a single card. The conditions are as follows.

The two cards must be next to each other in the row.
The level of the merged card equals the level of A. The level of the appended card B is gone.
The merged card stays where the two cards were and counts as one card in later merges.

Each merge pays gold equal to the sum of the levels of the two cards right before they are merged.

Merging continues until one card is left, so exactly $n-1$ merges happen. Find the largest total gold Yeonggwan can receive.

Take three cards $c_1, c_2, c_3$ with levels 40, 30, 30. Appending $c_2$ to $c_3$ leaves a card of level 30 and pays 60 gold. Appending that card to $c_1$ leaves a card of level 40 and pays 70 gold, for a total of 130. In the other order, appending $c_2$ to $c_1$ leaves a card of level 40 and pays 70 gold, and appending $c_3$ to that card pays 70 gold again, for a total of 140.

Input

The first line contains the number of cards $n$ ( $1 \le n \le 1000$ ).

The second line contains the levels $L_1, L_2, \dots, L_n$ of the $n$ cards, in the order they lie in the row ( $0 < L_i \le 100000$ ).

Output

Print the largest total gold on one line. If $n = 1$ , no merge happens, so print 0.

Examples4

Example 1
Input
```
3
40 30 30
```
Expected output
```
140
```
Example 2
Input
```
2
1 1
```
Expected output
```
2
```
Example 3
Input
```
5
100 1 2 3 4
```
Expected output
```
410
```
Example 4
Input
```
4
7 7 7 7
```
Expected output
```
42
```