Divide Crates for Minimal Weight Difference

You are given n crates with specific weights. Your task is to partition the crates into two groups such that the absolute difference between the total weights of the two groups is minimized. This problem can be formulated as follows:

where

Solve this problem using an efficient algorithm based on dynamic programming.

inputFormat

The input is read from stdin and consists of two lines. The first line contains an integer n (1 ≤ n ≤ 1000) representing the number of crates. The second line contains n space-separated integers, each representing the weight of a crate.

outputFormat

Output to stdout a single integer which is the minimum possible difference between the total weights of the two groups.## sample

5
1 2 3 4 5

1