Number Picking Game

Time limit1sMemory limit256 MB

Summary

Ahyeon removes interior numbers one at a time, scores each pick plus its live neighbors, and maximizes the total score.

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

Problem

Ahyeon plays a keyboard instrument, so Ahyeon builds up fingertip strength with a game about picking numbers. The rules are these.

Ahyeon is given a list of positive integers. Ahyeon can choose any number in the list except the first one and the last one. The chosen number disappears from the list, and the score goes up by the sum of the chosen number and the two numbers next to it. The game ends when only two numbers are left in the list.

Take the list 1 2 3 4 5. If Ahyeon picks 3, the score becomes $2+3+4=9$ and the list is 1 2 4 5. If Ahyeon then picks 4, the score becomes $9+2+4+5=20$ and the list is 1 2 5.

Given the list, find the highest score Ahyeon can reach.

Input

The input holds several test cases. Each test case is one line of the form $n$ $k_1$ $k_2$ $\ldots$ $k_n$ . Here $n$ is the count of numbers in the list and $3 \le n \le 200$ . Each integer $k_i$ satisfies $1 \le k_i \le 100$ . The last line holds a single $0$ , and reading that line ends the input.

Output

For each test case, print the highest score Ahyeon can reach on its own line.

Examples4

Example 1

Input

5 1 2 3 4 5
5 2 1 5 3 4
6 30 20 40 50 70 60
0

Expected output

30
31
570

Example 2
Input
```
3 1 1 1
0
```
Expected output
```
3
```

Example 3

Input

3 100 100 100
3 1 100 1
3 100 1 100
0

Expected output

300
102
201

Example 4

Input

4 1 2 3 4
4 4 3 2 1
4 1 100 100 1
4 100 1 1 100
0

Expected output