Minimum Difference Partition

You are given a list of coins where each coin has a certain positive value. Your task is to split the coins into two groups such that the absolute difference between the sums of the two groups is minimized. Formally, if you partition the coins into two sets (A) and (B), you need to minimize (|\sum_{a \in A} a - \sum_{b \in B} b|).

For example, if the coins are [1, 2, 7], one optimal partition is {1,2} and {7} which results in a difference of 4. This problem can be solved using exhaustive search with bitmasking since the number of coins is small.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) representing the number of coins. The second line contains (n) space-separated integers representing the values of the coins.

outputFormat

Output the minimum absolute difference between the sums of the two groups to standard output (stdout).## sample

3
1 2 7

4