To prepare for the rainy season, a group of engineers is reinforcing a series of water reservoirs on an island. The reservoirs are formed by natural rock columns arranged in a straight line. Each column has an initial height, and when it rains, water collects between the columns, creating storage areas like small basins.

To improve the reservoirs water capacity, the engineers are allowed to reinforce the rock columns by placing up to ~K~ unit-sized stone blocks. Each block increases the height of a column by 1 unit.

Water is retained only if it is trapped between taller columns on both sides. If water overflows a column, it is lost. Therefore, the goal is to carefully choose where to place the ~K~ blocks to maximize the total volume of water that can be held after reinforcement

Your task is to determine the maximum amount of water that can be stored after placing exactly ~K~ blocks in the most optimal way.

Input

• The first line contains two integers ~N~ and ~K~ ~(1 ≤ N, K ≤ 12)~ — the number of columns of rock and the number of available blocks.
• The second line contains ~N~ integers ~h_1, h_2,..., h_n ~ ~(1 ≤ h_i ≤ 10^{18})~ — the initial heights of the columns of rock.

Output

• A single integer — the maximum volume of water that can be stored after adding ~K~ blocks optimally.

📌 Example

Input

10 2
3 1 4 1 2 1 1 4 2 1

Output

17

💡 Explanation

This is the initial reservoir, which can store 13 blocks of water.

After placing up to ~K~ stone blocks (yellow blocks), the new reservoir can store ~4~ more blocks of water (green blocks).

So, the maximum volume of water that can be stored after adding ~2~ blocks optimally is 17 blocks of water.