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 unit-length width. Its length can be divided into $n$ sections of unit-length, 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 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.

9 2
1 4 1 2 2 4 1 2 1

11