006 - 2つの多角形

問題

ヤエさんは３本以上の真っすぐな棒を繋げて多角形を作り、恋人のジョウ君にプレゼントすることにしました。棒はそれらの端点でのみ繋げることができます。端点はすべて同じ平面上に置きます。一つの接合点で繋がる棒は２本だけで、それらがなす角度は自由に決めることができます。

ヤエさんは、自分が持っている棒をすべて使って大きさが同じくらいの２つの多角形を作ろうとしています。

与えられたすべての棒を使って、２つの多角形を、それらの周囲の長さの差の絶対値が最小となるように作る。各棒の長さが与えられたとき、２つの多角形の周囲の長さの差の絶対値を求めるプログラムを作成せよ。２つの多角形を作成できない場合はそのことを報告せよ。ただし、長さが$a_1 \leq a_2 \leq ... \leq a_m$である$m$ ($3 \leq m$)本の棒で、$a_m ＜a_1+a_2+ ... +a_{m-1}$を満たすとき、これら$m$本の棒でひとつの多角形を作成できるものとする。

入力

入力は以下の形式で与えられる。

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

１行目に棒の数$N$ ($6 \leq N \leq 40$)が与えられる。２行目に各棒の長さ$a_i$ ($1 \leq a_i \leq 100$)が与えられる。

出力

与えられたすべての棒を使って２つの多角形を作れる場合は、長さの差の絶対値の最小値を１行に出力する。２つの多角形を作れない場合は「-1」を１行に出力する。

入出力例

入力例１

6
2 2 3 2 2 2

出力例１

1

入力例２

7
2 2 3 2 2 2 1

出力例２

0

入力例３

6
1 1 1 1 2 4

出力例３

-1