题目描述

有 $N$ 个细胞排成一行。细胞编号从 $1$ 到 $N$，从左到右。

最初，所有细胞都是空的。你可以任意次数以任意顺序执行以下两种操作：

• 选择三个连续的空细胞，并在每个细胞上放置一个硬币。
• 选择三个连续有硬币的细胞，并移除选中细胞上的所有三个硬币。

当你完成操作后，如果第 $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 表示有硬币的细胞，用 .（点）表示没有硬币的细胞。一种最优的方法如下：

.... $\\rightarrow$ .ooo

这样我们能够得到 $2 + 3 + 4 = 9$ 分。

示例输入2

6
3
-2
-1
0
-1
4

示例输出2

6

一种最优的方法如下：

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