Minimum Weight Difference Partition

You are given N marbles with weights w₁, w₂, ..., w_N. Your task is to divide these marbles into two bags such that the absolute difference between the total weights of the two bags is minimized.

Let \(S = \sum_{i=1}^{N} w_i\) be the total weight. We need to find a subset of marbles with total weight as close as possible to \(\frac{S}{2}\). The answer is the minimum possible difference, computed as \(S - 2\times\text{subset_sum}\) where subset_sum is the maximum weight not exceeding \(\frac{S}{2}\).

This is a classic problem that can be solved using dynamic programming.

inputFormat

The input is read from standard input (stdin) and has the following format:

N
w1 w2 ... wN

Where:

• N is an integer representing the number of marbles.
• wi is the weight of the i-th marble.

outputFormat

The output is written to standard output (stdout) and is a single line containing the minimum weight difference achievable.

## sample

1
10

10

</p>