Falling Apart

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.

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$)

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