0704. Stone Pile

Time limit : 1000 ms Memory limit : 64 mb

You have a number of stones with known weights w1, …, wn. Write a program that will rearrange the stones into two piles such that weight difference between the piles is minimal.

Input

Input contains the number of stones n (1 ≤ n ≤ 32) and weights of the stones w1, …, wn (integers, 1 ≤ wi ≤ 107) delimited by white spaces.

Output

Your program should output a number representing the minimal possible weight difference between stone piles.

Sample

 № Input Output 1 55 8 13 27 14 3