Falling Apart

Time limit2sMemory limit512 MB

Summary

Given up to 15 positive integers, two players alternately take one piece; find the final sums under optimal play.

Level: Easy3 of 10
Topics: Dynamic programming, Game theory, Bit manipulation
Solved: No attempts yet

Problem

Alice and Bob bought a very large integer, showed it off at a party, and carried it home together because it was too big for one person. On the way, both of them stumbled. The integer hit the pavement and broke into $n$ positive integer pieces.

The purchase had already left them short on money, and after this they decided to separate. They divide the remaining pieces with a game. They take turns picking one piece at a time until no piece is left, and Alice picks first.

Each of them wants the sum of the pieces they take to be as large as possible, and both play optimally. Compute the total each of them ends up with.

Input

The input consists of two lines.

The first line contains the number of pieces $n$ . ( $1 \le n \le 15$ )

The second line contains the values of the pieces $a_0, a_1, \dots, a_{n-1}$ , separated by spaces. ( $1 \le a_i \le 100$ )

Output

Print one line with the combined value of Alice's pieces and the combined value of Bob's pieces, separated by a space.

Examples2

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