Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

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 ith 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
  • 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