Tow Polygons

　

Yae decided to make a polygon by connecting three or more straight sticks and give it to her boyfriend, Jo. The sticks can only be connected at their end points. All end points must be on the same plane. Only two sticks can be connected at a single junction point, and the angle between them can be determined freely.

Yae is trying to make two polygons of equal size using all the sticks she has.

Using all the given sticks, make two polygons such that the absolute value of the difference between the lengths of their perimeters is minimized. Given the length of each stick, write a program to find the absolute value of the difference in the lengths of the perimeters of the two polygons. If you cannot create two polygons, report it. For $m$ ($ \leq 3$) sticks of length $a_1 \leq a_2 \leq ... \leq a_m$, if $a_m ＜a_1+a_2+ ... +a_{m-1}$, we can create a polygon with these $m$ sticks.

Input

The input is given in the following form.

$N$ 
$a_1$ $a_2$ ... $a_N$

The first line gives the number of sticks $N$ ($6 \leq N \leq 40$). The second line gives the length of each stick $a_i$ ($1 \leq a_i \leq 100$).

Output

If two polygons can be constructed using all the given sticks, output the minimum absolute value of the difference in length in a line. If two polygons cannot be constructed, output "-1" in a line.

Sample Input and Output

Sample Input 1

6
2 2 3 2 2 2

Sample Output 1

1

Sample Input 2

7
2 2 3 2 2 2 1

Sample Output 2

0

Sample Input 3

6
1 1 1 1 2 4

Sample Output 3

-1

---