Given *n* natural numbers,
find how to separate them into two sets
so that the absolute value
of the difference between the sums of the elements of the two sets is minimized.

**Input**

Input consists of several cases,
each with *n* followed by *n* natural numbers between 1 and 10^{6}.
Assume 1 ≤ *n* ≤ 23.

**Output**

For every case, print the minimum possible difference.

Public test cases

**Input**

5 18 10 19 14 3 4 1000 10 10 10 1 20 7 1 2 4 8 16 32 64

**Output**

0 970 20 1

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++