##### 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 representing the number of weights you have. The next lines each contain a number 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

## Comments

This question is misleading by the note: the trivial solution of having zero weight in both hands is not acceptable ;)

This note means that you can't hold nothing, but it may also lead you to think that you don't have to hold all the weights... But that's not the case. The question actually expects you to hold everything on your hand.

I believe your observation is wrong.

My solution did not use the fact that you need to hold ALL the weights.

However, you need to consider all the weights.

Do you have proof that not holding all the weights is bad?