No tags yet

No tag edit access

Time limit per test: 0.25 second(s)

Memory limit: 65536 kilobytes

Memory limit: 65536 kilobytes

input: standard

output: standard

output: standard

For most people Halloween evening is a time of having fun. But Mr. X chose the night after Halloween to commit a crime. He wants to get some boards to build a shed. And he decided to stole it from the fence of the neighbouring factory. But he wants to do it in such a way that nobody will notice boards loss. The fence consists of several boards with width, equal to 1, and integer heights (see picture). Mr. X is going to take some boards from the fence and then put the remaining boards together without changing their order to form a new fence. To be sure that noboby will notice the change, the perimeter of resulting fence should not be less than a half of the perimeter of initial fence. See picure description to understand the way of calculating fence's perimeter. With such constraint, Mr. X wants to maximize total height of extracted boards.

Perimeter of the fence is a perimeter of the figure, which is made by joining the rectangles corresponding to boards. For example, perimeter of the fence in the picture is marked bold and it's length is equal to 24.

sample input | sample output |

6 3 4 2 4 3 1 | 12 4 1 3 4 5 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2019 22:28:47 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|