DWITE Online Computer Programming Contest, February 2011, Problem 3

Being the star attraction of the local carnival, it's your job to come up with new acts for every show. For the next show, you decided that you would give a shot at riding a unicycle while balancing weights on both your hands. To make sure that you don't fall, you want the weights in your hands to balance out as much as possible (i.e. the difference between the sum of the weights in either of your hands must be as small as possible). Given the weights you have, determine the smallest difference in weight between your left and right hands.

The input will contain 5 test cases. The first line contains a number ~N~ ~(1 \le N \le 30)~ representing the number of weights you have. The next ~N~ lines each contain a number ~W~ ~(1 \le W \le 1000)~ representing how heavy each weight is.

The output should contain 5 lines, each line representing the minimum difference of weight between your two hands.

Note: the trivial solution of having zero weight in both hands is not acceptable ;)

Sample Input

3
1
10
6
5
9
4
5
7
1

Sample Output

3
0

Problem Resource: DWITE