Training Site

# Betty the Cat

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 1.0 seconds

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.

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

9
6 7 5 4 8 9 4 6 7


### Sample Output 1

48

• ### Sample Input 2

20
1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1


### Sample Output 2

12