配点 : $800$ 点

問題文

$N$ 個のマスが一列に並んでおり、左から右に $1$ から $N$ までの番号が振られています。

はじめ、すべてのマスは空です。 あなたは、以下の $2$ 種類の操作を任意の順に何度でも行うことができます。

• 連続する $3$ マスであってコインが置かれていないものを選び、それぞれにコインを置く。
• 連続する $3$ マスであっていずれにもコインが置かれているものを選び、それぞれからコインを取り除く。

操作を済ませた後、左から $i$ マス目にコインが置かれているなら、$a_i$ 点が得られます。 コインがあるマス全てから得られる点数の合計が、あなたの得点です。

得られる最高得点を求めてください。

制約

• $3 \leq N \leq 500$
• $-100 \leq a_i \leq 100$
• 入力中の全ての値は整数である。

入力

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

$N$

$a_1$

$a_2$

$:$

$a_N$

出力

答えを出力せよ。

4
1
2
3
4

9

コインが置かれたマスを o で、置かれていないマスを . で表します。 最適な手順の $1$ つは次の通りです。

.... $\rightarrow$ .ooo

このようにすれば、$2 + 3 + 4 = 9$ 点を得られます。

6
3
-2
-1
0
-1
4

6

最適な手順の $1$ つは次の通りです。

...... $\rightarrow$ ooo... $\rightarrow$ oooooo $\rightarrow$ o...oo

このようにすれば、$3 + (-1) + 4 = 6$ 点を得られます。

10
-84
-60
-41
-100
8
-8
-52
-62
-61
-76

0