No.18 おまんじゅうわけわけ

時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

あるお土産屋では$N$個の袋入りまんじゅうを売っていて、i個目の袋には$Ai$個のまんじゅうが入っています。 C3H5(ONO2)3君はいくつかの袋を買いたいですが、3人に配るときにまんじゅうのあまりを出したくないです。 そのように買えるとき、まんじゅうの個数の最大値を求めてください。 また、できない場合は$-1$を出力してください。

制約

• $1 ≦ N ≦ 100000$
• $1 ≦ Ai ≦ 1000$

入力形式

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

N
A1 A2 A3 ... An

出力

まんじゅうの個数の最大値を出力してください。

入出力例

3
3 6 9

18

3,6,9個入りの袋を選べばいいので$3 + 6 + 9 = 18$です。

4 
1 2 3 4

9

2,3,4個入りの袋を選べばいいので$2 + 3 + 4 = 9$です。

2 
4 7

-1

どのように選んでもあまりがでてしまうので$-1$を出力してください。