Team Dessert

Time limit1sMemory limit128 MB

Summary

Desserts sit in a row; two alternating teams take from either end, and the first-picking team wants the smallest total weight it can guarantee against optimal play.

Level: Medium7 of 10
Topics: Dynamic programming, Game theory, Array, Intervals
Solved: No attempts yet

Problem

Dieting can be lonely and dull, so a company called Olympic Slimmers Inc. (OSI) has turned it into a team sport. Their first game is the Team Dessert challenge.

A row of dessert dishes is placed on a long table, each labelled with its weight. The players are split into two teams, and they take desserts one at a time, alternating between the two teams. For example, with teams Red and Blue, if Blue picks first the order of picks is Blue, Red, Blue, Red, and so on.

There is one rule about which dessert you may take: on your turn you must take a dessert from one of the two ends of the row. So every choice is between just two dishes (except the final pick, where only one dish remains).

The two teams are as equal in size as possible. If the sizes cannot be equal, the larger team picks first.
Every player takes exactly one dessert.
The number of desserts equals the number of players.

The team with the smallest total dessert weight wins.

Given the weights of the desserts in the order they are placed, determine the best strategy for the team that picks first. Compute the smallest total weight this team can guarantee for itself, assuming the opposing team also plays optimally. (Guaranteeing this total does not necessarily mean winning.)

Input

The input contains several test cases.

Each test case begins with a line containing a single integer $N$ , the number of players ( $1 \le N \le 1000$ ). The value $N = 0$ marks the end of the input and is not a test case.

The following lines list the weights of the $N$ desserts, in the order they are placed on the table. Each weight $W$ satisfies $1 \le W \le 100$ . There is at least one weight per line, and no line is longer than 80 characters. Weights are separated by one or more spaces, and a line may have leading or trailing spaces.

Output

For each test case, output a single line containing one integer: the minimum total dessert weight that the first-picking team can guarantee, assuming the opposing team plays optimally.

Examples5

Example 1

Input

Expected output

19
30
11

Example 2
Input
```
1
50
0
```
Expected output
```
50
```
Example 3
Input
```
2
1 100
0
```
Expected output
```
1
```
Example 4
Input
```
3
1 2 3
0
```
Expected output
```
4
```
Example 5
Input
```
2
100 1
3
3 1 2
1
42
0
```
Expected output
```
1
5
42
```