A foundry must divide n metal billets between two crucibles. Every billet goes into exactly one crucible; a crucible may end up empty. Each billet has a whole-number mass. Assign the billets so that the absolute difference between the two crucibles' total masses is as small as possible, and report that minimum difference.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the billet masses.
Output format
A single integer: the minimum achievable absolute difference between the two totals.
Constraints
- 1 <= n <= 40
- 1 <= each mass <= 1000