Combining Riceballs

Time limit2sMemory limit512 MB

Summary

Given a row of riceballs, merge equal adjacent pairs or equal pairs with one ball between them, and find the largest size reachable.

Level: Medium7 of 10
Topics: Dynamic programming, Intervals, Prefix sum, Recursion
Solved: No attempts yet

Problem

Alphonse has N riceballs of various sizes lined up in a row. He wants to make the largest riceball he can for his friend. Alphonse can use the following two operations.

If two riceballs of the same size are next to each other, he can combine those two into one new riceball. The new riceball's size is the sum of the two sizes, and it takes the place the two old riceballs occupied.
If two riceballs of the same size have exactly one riceball between them, he can combine all three into one new riceball. The middle riceball does not have to match the other two in size. The new riceball's size is the sum of the three sizes, and it takes the place the three old riceballs occupied.

He can use each operation as many times as he wants.

Find the size of the largest riceball left in the row after 0 or more operations.

Input

The first line contains the integer N ( $1 \le N \le 400$ ).

The second line contains N space separated integers giving the sizes of the riceballs in order from left to right. Each integer is at least 1 and at most 1,000,000.

Output

Print the size of the largest riceball Alphonse can form.

Examples2

Example 1
Input
```
7
47 12 12 3 9 9 3
```
Expected output
```
48
```
Example 2
Input
```
4
1 2 3 1
```
Expected output
```
3
```