Question

In the strong room of ABC bank there are N vaults in a row. The amount of money inside each vault displayed on the door. You can empty any number of vaults as long as you do not empty more than 2 out of any 5 adjacent vaults. For example, of the vaults 1, 2, 3, 4, 5, if you empty 4 and 5, then you can not empty any of the vaults 6, 7 or 8 but you can empty 9th vault. If you attempt to break more than 2 of any 5 adjacent vaults, an alarm sounds and the sentry, a sharp shooter will kill you instantly with his laser gun!

The output is the maximum amount of money that can be emptied without sounding the alarm

Input

The first line contains an integer N which is the number of vaults. The next line has a sequence of positive integers of length N, giving the amount of cash in the vaults in order

Output

The maximum amount of money that can be looted without sounding the alarm.

Constraints

N≤50, Amount in each vault ≤50000

Example 1

Input:
9
1000, 2000, 1000, 5000, 9000, 5000, 3000, 4000, 1000

Output:
15000

Explanation:
One possible set of vaults to be looted to get the maximum possible are vaults 4, 5, 9 are looted, giving a total loot of (5000+9000+1000)=15000. Hence the output is 15000.

Example 2

Input:
10
5000,7000,3000,5000,9000,7000,6000,4000,7000,5000

Output:
28000

Explanation:
One possible set of vaults to be looted are (2, 5, 9, 10) Note that no set of five consecutive vaults has more than two vaults looted. The total looted is (7000 + 9000 + 7000 + 5000=28000). The out put is hence 28000.

Answer 1

what is the question my friend