1390 - 2つの多角形

時間制限 1 秒 / メモリ制限 256 MB / 得点 8 / Writer syoribu / x 0 / 統計 /


TLE
1sec
MLE
256MB
得点
8

問題

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

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

与えられたすべての棒を使って、2つの多角形を、それらの周囲の長さの差の絶対値が最小となるように作る。各棒の長さが与えられたとき、2つの多角形の周囲の長さの差の絶対値を求めるプログラムを作成せよ。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$

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

出力

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

入出力例

入力例1

6
2 2 3 2 2 2

出力例1

1

入力例2

7
2 2 3 2 2 2 1

出力例2

0

入力例3

6
1 1 1 1 2 4

出力例3

-1