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

Input contains the number of stones n (1 ≤ n ≤ 20) and weights of the stones w₁, …, w_n (integers, 1 ≤ w_i ≤ 100000) delimited by white spaces.

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