PEG Test – Oct 3rd, 2014

Korra is trying to restore balance to the world. But before that, she must restore balance in some numbers. Given ~N~ ~(1 \le N \le 10)~ numbers, Korra wants to split them into two (possibly empty) groups, such that their sums are as close as possible.

Output the minimum difference between the two groups of numbers.

Input Specification

The first line will contain the integer ~N~, representing the number of numbers Korra has.
The second line will contain ~N~ positive integers (each no greater than ~1\,000~), the numbers that Korra is trying to split.

Output Specification

Output a single line containing a single integer – the minimum difference of the sum of the two groups of numbers.

Sample Input 1

5
8 12 16 100 20

Sample Output 1

44

Sample Input 2

9
1 8 5 9 7 2 3 4 6

Sample Output 2

1