Betty the Cat

Betty is a very peculiar cat, who likes to spend her days basking in sunny spots, but has some particular rules about which spots to choose.

She divides her day into $P$ ($1 \leq P \leq 1000000$) basking periods. Every morning she checks the weather forecast and determines the optimal sunny spot for each basking period throughout the day. Each basking period is thus assigned a value $V_i$, ($0 \leq V_i \leq 1000$ for $1 \leq i \leq P$)

She then wishes to select some subset of those basking periods to maximise the total value, subject to the following constraint: to prevent dehydration, she must not bask for any four consecutive basking periods.

For example, suppose she divides her day into $9$ basking periods with values $6, 7, 5, 4, 8, 9, 4, 6, 7$ in order. Selecting the basking periods:

6 7 5 4 8 9 4 6 7
* * *   * * * * *

would result in dehydration, and so is invalid, due to the five consecutive basking periods at the end. The correct solution for this input can be seen to be, giving a total of 48:

6 7 5 4 8 9 4 6 7
* * *   * *   * *

Help Betty to find the maximum total value of basking she can attain, without becoming dehydrated.

Input

The first line of input will consist of a single integer $P$, the number of basking periods.

The second line of input will contain $P$ integers $V_i$, each describing the value of the $i$th basking period.

Output

Output a single line containing a single integer - the maximum total value of basking that Betty can attain.

Subtasks

The following subtasks are available:

• Subtask 1 ($20\%$): $0 \leq V_i \leq 1$
• Subtask 2 ($40\%$): $P \leq 20$
• Subtask 3 ($40\%$): No further restrictions