Internet Problem Solving Contest

IPSC 2000

Problem R – Santo's Bottles

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 should he drink out because thinking is making him nervous.

Input file description

The first line of the input file 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.

Output file description

The output file contains a single integer - the maximum total volume of alcohol that can Santo drink, obeying to the rule that the must leave at least one full bottle among any three consecutive bottles.


Input file:
Output file:

(He should drink the first, second, fourth and fifth bottle.)