Wrestling Team Selection

Interview

Time limit1sMemory limit128 MB

Summary

Split up to 100 wrestlers into two teams of nearly equal size so the total weights differ as little as possible.

Level: Medium5 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

The national wrestling association is dividing its athletes into two teams for the upcoming Olympic trials.

Every athlete belongs to exactly one of the two teams. The sizes of the two teams differ by at most 1. Under those conditions, the difference between the two total weights must be as small as possible.

Given the weight of every athlete, divide them into teams as described and compute the total weight of each team.

Input

The first line contains the number of athletes $n$ . Each of the next $n$ lines contains the weight of one athlete, an integer that is at least $1$ and at most $450$ . The association has no more than $100$ athletes.

Output

Print the total weight of the two teams on one line, separated by a space. Print the smaller total first.

Examples1

Example 1
Input
```
3
100
90
200
```
Expected output
```
190 200
```