You have a number of stones with known weights *w*_{1}, …, *w*_{n}. 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* ≤ 20) and weights of the stones *w*_{1}, …, *w*_{n} (integers, 1 ≤ *w*_{i} ≤ 100000) delimited by white spaces.

### Output

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

### Sample

input | output |
---|

5
5 8 13 27 14
| 3 |

**Problem Source: **USU Championship 1997