11835번 - Skyline 다국어

You want to have in your city a beatiful skyline. You have decided to build N skyscrapers in a straight row. The i-th of them should have exactly h[i] floors.

You have got offers from different construction companies. One of them offers to build one floor in any of the skyscrapers for 3 Million Euros. The other one offers to build one floor in each of two neighbouring skyscrapers for 5 Millions in total. Note that it doesn’t matter whether these floors are on the same height or not. The third one can build one floor in each of three consecutive skyscrapers for only 7 Millions.

You can build the floors in any order you want. Calculate the minimal possible total amount of money needed to finish the construction.

The first line contains integer number N (1 ≤ N ≤ 300). The second line contains space separated N integer numbers, h[1], h[2], ..., h[N], 1 ≤ h[i] ≤ 200.

Output one integer number: the amount of money, in Millions.