Problem Description

Translated from CCC2016 Senior T4 "Combining Riceballs"

Alphonse has \( N \) delicious riceballs of varying sizes arranged in a row. He wants to give the largest riceball to his best friend. He can perform the following operations:

• If two adjacent riceballs are of the same size, Alphonse can merge them into a new riceball. The new riceball's size is the sum of the sizes of the two original riceballs. It will occupy the positions previously occupied by the two original riceballs.

• If two riceballs are of the same size and there is only one riceball between them, Alphonse can also merge them into a new riceball. (The size of the middle riceball is not specified.) The new riceball's size is the sum of the sizes of the three original riceballs and it will occupy the positions previously occupied by the three original riceballs.

Alphonse can perform these operations as many times as he wishes.

After performing zero or more operations, determine which riceball he should give to his best friend.

Input Format

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

The second line contains \( N \) space-separated integers representing the sizes of the riceballs in order from left to right. Each integer is at most \( 1,000,000 \).

Output Format

Output the largest size of the riceball that Alphonse can obtain.

Sample Input and Output

Sample Input #1

7
47 12 12 3 9 9 3

Sample Output #1

48

Sample Input #2

4
1 2 3 1

Sample Output #2

3

Notes

Sample Explanation 1

One possible merging scheme is: merge the two riceballs of size \( 12 \) to get a riceball of size \( 24 \). Then merge the two riceballs of size \( 9 \) to get a riceball of size \( 18 \). Next, merge the three riceballs of sizes \( 3, 18, \) and \( 3 \) to get a riceball of size \( 24 \). Finally, merge the two riceballs of size \( 24 \) to get a riceball of size \( 48 \).

Sample Explanation 2

No operations can be performed, so the answer is \( 3 \).

For \( \frac{1}{15} \) of the data, \( N = 4 \).

For another \( \frac{2}{15} \) of the data, \( N \le 10 \).

For another \( \frac{5}{15} \) of the data, \( N \le 50 \).

见题面 Input 部分

见题面 Output 部分