問題文

$N$ 個のりんごがあります。りんご $i$ の重さは $A_i$ です。また、$3$ 枚の皿があり、それぞれ赤, 緑, 青の色で塗られています。

あなたは $N$ 個全てのりんごを、それぞれ赤, 緑, 青のいずれか $1$ つの皿に乗せます。

赤, 緑, 青の皿に乗っているりんごの重さの和をそれぞれ $R,G,B$ として、以下の $2$ つの条件を満たすように乗せる必要があります。

• どの皿にもりんごが $1$ 個以上乗っている。
• $G=B$ である。

$R$ として考えられる最大値を求めて下さい。条件を満たすりんごの乗せ方が無い場合はそれを報告してください。

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

• $3 \leq N \leq 3000$
• $1 \leq A_i \leq 5000$
• 入力は全て整数

出力

答えを整数で出力してください。 条件を満たすりんごの乗せ方が無い場合は -1 と出力してください。

サンプル

5
1 2 3 4 5

9

3
1 2 3

-1

11
59 927 349 933 1451 453 2000 975 345 782 123

4733