Santo has won a bet against the landlord of the largest (in fact, the only) saloon in New Clondike. Today he came into the saloon to get his prize. The landlord put several bottles in a row on the bar before him. The bottles were of different volumes and to Santo's pleasure they all contained various spirits. The landlord said: "You can drink from these bottles as much as you can, Santo. But if open a bottle, you must drink it out before you touch another one. After you are finished with it, you must return it to its original position. And the most important thing: you may not drink from any three consecutive bottles, it brings bad luck!

The poor Santo is now standing at the bar and thinking hard, which bottles should he drink out such that he would have drunken as much alcohol as possible. Please help him find out which bottles he should drink out because thinking is making him nervous.

Input

The first line of each test case contains a single integer N - the number of bottles. Next N lines contain one integer each, line i+1 containing number vi - volume of the i-th bottle. You may assume that N will be no more than 700.

There are multiple test cases. The last test case is followed by a negative number, which should not be processed.

Output

Output for each test case a single integer - the maximum total volume of alcohol Santo can drink, obeying to the rule that he must leave at least one full bottle among any three consecutive bottles.

Sample Input

6
6
10
13
9
8
1

5
1
2
8
3
4

-1
Sample Output
33
14

(In the first case, he should drink the first, second, fourth and fifth bottle. In the second one, he should drink the second, third and fifth bottle.)