Problem F (Northern European ACM Regional): Dividing coins

Description

Dutch legend has it that copper-wire was invented in Holland when a husband and wife were fighting over a copper coin. (after the tulip crash of the 1600's.) The fighting was so fierce, they stretched the coin to a great length and thus created the first conductor. Not as commonly known is that the fighting started after the couple tried to divide a bag with coins between the two of them. The contents of the bag appeared not to be equally divisible. They couldn't stand the fact that a division should favour one of them and they always wanted a fair share to the very last cent. Nowadays fighting over a single cent is unlikely, but being capable of making a division as fair as possible is something that will remain important forever... . Your task is to solve this problem.

Problem

Given a bag with a maximum of 100 coins, determine the fairest division between two persons. This means that the difference between the amount each person obtains should be minimized. The value of a coin varies from 1 cent to 500 cents. It's not allowed to split a single coin.

Input

The above input may be repeated a number of times.

Output

There is one line of output for each pair of input lines. Each output line is simply the minimal positive difference between the amount the two persons obtain when they divide the specified coins as equitably as possible.

Example

Sample input

3
2 3 5
4
1 2 4 6

Correct output for the sample input

0
1