Lifeboat Balancing

Time limit1sMemory limit128 MB

Summary

Split all passengers into two boats with equal head counts (off by one when N is odd) so the two total weights differ as little as possible.

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

Problem

A large cruise ship with plenty of design flaws has begun to sink on its first voyage. Two lifeboats hang on the side, and each one holds half of the passengers. A lifeboat that carries far more weight than the other risks sinking, so the two loads have to be as close as possible.

All $N$ passengers must board a lifeboat, and both lifeboats must carry the same number of people. When $N$ is odd an even split is impossible, so one boat takes $\lfloor N/2 \rfloor$ people and the other takes $\lceil N/2 \rceil$ . Under that rule, report the two loads that make the difference between the boats as small as possible.

Input

The first line has $C$ , the number of test cases.

The first line of each test case has $N$ , the number of people who must board ( $1 \le N \le 5000$ ). Each of the next $N$ lines has one passenger weight $W$ ( $1 \le W \le 1000$ ).

Output

For each test case print the two loads of the most balanced distribution on one line. If the two loads differ, print the smaller one first. Separate the two numbers with a single space.

Examples3

Example 1

Input

Expected output

25 30
31 34

Example 2
Input
```
1
4
1
1
1
7
```
Expected output
```
2 8
```
Example 3
Input
```
1
1
500
```
Expected output
```
0 500
```