Problem J
Just Enough Water
As you may remember, in The $2\, 016$ ICPC Nha Trang Regional Contest, the problem Reservoir, we have built a reservoir near the Red River. The reservoir can be viewed as a rectangular box with unitlength width. Its length can be divided into $n$ sections of unitlength, the $i$th section having height of $h_ i$ units. We assume that the left and right of the reservoir has height of $0$, i.e. $h_0 = h_{n+1} = 0$.
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:
In the above picture:

$n = 9, h = [1, 4, 1, 2, 2, 4, 1, 2, 1]$.

The reservoir is filled with $8$ 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 $1$ dollar to raise the height of one section by $1$ unit. We have a total budget of $k$ dollars.
What is the maximum number of units of water the reservoir can hold?
Input

The first line contains two integers $n$ and $k$ $(1 \le n, k \le 12)$.

The second line contains exactly $n$ integers $h_1, h_2, \ldots , h_ n$ $(1 \leq h_ n \leq 10^9)$, representing the height of $n$ 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 abovementioned 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.
Sample Input 1  Sample Output 1 

9 2 1 4 1 2 2 4 1 2 1 
11 