Big_Persimmon — OOI final
Task type: batch | Time limit: 2 s | Memory limit: 1024 MB | Difficulty: 27
Algorithms: memoization, game theory, interval dp, dynamic programming

# Big Persimmon

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 2 seconds       |
| Memory limit: | 1024 megabytes  |

Alice and Bob bought a big persimmon, cut it into $n$ pieces with sizes $w_1, ..., w_n$, and immediately started eating it. The kids will eat the pieces simultaneously, and for each of them, the eating process is as follows:

As soon as someone finishes eating their previous piece (and at the beginning of the meal), they choose the next piece and start eating it. If a piece of size $w$ is taken, it will take exactly $w$ seconds to eat it, and then it will be time to choose a new piece. If both finish eating their previous piece at the same time (or if the eating just started), Alice will choose the first piece, but they will start eating at the same time. Choosing a new piece does not take time.

Since both Alice and Bob are perfectionists, when they choose a piece, they will take either the smallest (with the smallest $w_i$) or the largest (with the largest $w_i$) from all the remaining pieces.

The eating process ends when the last person finishes eating and there are no more pieces left.

Both Alice and Bob are interested in eating as much as possible. Find the total size of the pieces that Alice will eat and the total size of the pieces that Bob will eat, if they both choose the pieces optimally.

## Input

The first line contains a single integer $n$ ($1 \le n \le 2000$) — the number of persimmon pieces.

The second line contains $n$ integers $w_1, w_2, ..., w_n$ ($1 \le w_i \le 20\,000$, $w_i \le w_{i+1}$) — the sizes of the persimmon pieces.

Let $W$ denote the sum of the sizes of all the pieces. It is guaranteed that $W \le 20\,000$.

## Output

In a single line, output two numbers — the total size of the pieces that Alice will eat and the total size of the pieces that Bob will eat, if they both choose the pieces optimally.

### Examples

| standard input | standard output |
|----------------|-----------------|
| 5<br>1 1 3 4 6 | 8 7             |
| 4<br>1 1 2 2   | 3 3             |
| 4<br>1 7 7 9   | 10 14           |

## Note

In the first example, Alice should first take a piece of size 1. Immediately after that, Bob should also take a piece of size 1. After a second, Alice will take a piece of size 3, and then Bob will take a piece of size 6. 3 seconds later, Alice will take a piece of size 4. 3 seconds later, Bob will finish eating, and a second later the process will finish. At this point, Alice will eat pieces of sizes 1 + 3 + 4 = 8, and Bob: 1 + 6 = 7.

In the third example, Alice should take a piece of size 1, and Bob should take a piece of size 7. After a second, Alice will take a piece of size 9, and 6 seconds later, Bob will take a piece of size 7.

## Scoring

The tests for this problem consist of four groups. Points for each group are given only if all tests of the group and all tests of the required groups are passed. Note that passing the example tests is not required for some groups. Offline-evaluation means that the results of testing your solution on this group will only be available after the competition.

| Group | Points | $n$         | $w_i$       | Required Groups | Comment                                       |
|-------|--------|-------------|-------------|-----------------|-----------------------------------------------|
| 0     | 0      | -           | -           | -               | Examples.                                     |
| 1     | 10     | $n = 3$     | -           | -               |                                               |
| 2     | 12     | -           | $w_i \le 2$ | -               |                                               |
| 3     | 19     | $n \le 200$ | $w_i \le 500$| 0               |                                               |
| 4     | 15     | $n \le 500$ | $W \le 5000$ | -               | $w_{i+1} \le 2 \cdot w_i$ for all $1 \le i \le n - 1$ |
| 5     | 13     | -           | -           | 2, 4            | $w_{i+1} \le 2 \cdot w_i$ for all $1 \le i \le n - 1$ |
| 6     | 31     | -           | -           | 0 – 5           | Offline-evaluation.                           |

Starter code: