Splitting Teams Fairly

Interview

Time limit1sMemory limit128 MB

Summary

Split N people into two teams differing in size by at most one so their total weight difference is minimized, then print both totals in increasing order.

Level: Medium5 of 10
Topics: Dynamic programming, Array, Math, Brute force
Solved: No attempts yet

Problem

The student council president wants to hold a tug-of-war at the school festival to help classmates bond.

To keep the match fair, the two teams may differ in size by at most one person, and under that condition the teams must be split so that the difference between the total weights of the two teams is as small as possible.

Print the total weight of each of the two resulting teams.

Input

The first line contains the number of participants $N$ ( $1 \le N \le 100$ ).

Each of the next $N$ lines contains one person's weight $K$ ( $1 \le K \le 450$ ).

Output

Print the total weights of the two teams in increasing order, separated by a single space.

Examples1

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