Vasya and Petya went to dig potatoes. At the end of the day they dug up N sacks of potatoes weighing W
1, W
2, ... W
N. How can they divide the sacks of potatoes among themselves so that the mass difference is minimal.
Input
On the first line the number N is written – number of bags (1 ≤ N ≤ 18). The second line lists the masses of bags W1, W2 , … WN (1 ≤ Wi ≤ 105).
Output
On a single line, print one non-negative integer – the minimum possible difference between the masses of two heaps with bags.
| Input |
Output |
5
5 3 5 7 8
| 2 |
for;while;until