Problem Statement

$N$ cells are arranged in a row. The cells are numbered $1$ through $N$ from left to right.

Initially, all cells are empty. You can perform the following two types of operation arbitrary number of times in arbitrary order:

• Choose three consecutive empty cells, and put a coin on each of the three cells.
• Choose three consecutive cells with coins, and remove all three coins on the chosen cells.

After you finish performing operations, if the $i$-th cell contains a coin, you get $a_i$ points. Your score is the sum of all points you get from the cells with coins.

Compute the maximum possible score you can earn.

Constraints

• $3 \leq N \leq 500$
• $-100 \leq a_i \leq 100$
• All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1
a_2
:
a_N

Output

Print the answer.