Problem J
Just Enough Water
As you may remember, in The
After the rain, some of the sections of the reservoir are filled with water. Naturally, water flows from higher places to lower places, so water flows to both the left and the right of the reservoir.
An example of the cross section of the reservoir along its length and height dimensions is shown in the following illustration:
![\includegraphics[width=0.4\textwidth ]{J.jpg}](/problems/justenoughwater/file/statement/en/img-0001.jpg)
In the above picture:
-
. -
The reservoir is filled with
units of water.
It was found that the reservoir does not hold enough water,
thus we have decided to raise the height of some sections. It
costs
What is the maximum number of units of water the reservoir can hold?
Input
-
The first line contains two integers
and . -
The second line contains exactly
integers , representing the height of sections.
Output
Print a single integer — the maximum amount of water the reservoir can hold.
Explanation of the first sample
Initially, the reservoir looks like the above-mentioned figure. The figure below demonstrates an optimal way to maximize the amount of water that the reservoir can hold. Yellow cells show how we raise sections’ height. Green cells show extra water that the reservoir can hold.
![\includegraphics[width=0.4\textwidth ]{J2.jpg}](/problems/justenoughwater/file/statement/en/img-0002.jpg)
Sample Input 1 | Sample Output 1 |
---|---|
9 2 1 4 1 2 2 4 1 2 1 |
11 |