問題文

$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$

出力

答えを出力せよ。

入力例 1

4
1
2
3
4

出力例 1

9

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

.... $\\rightarrow$ .ooo

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

入力例 2

6
3
-2
-1
0
-1
4

出力例 2

6

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

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

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

入力例 3

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

出力例 3

0