Mountain Trek Route

A circular mountain cycling trek route was built in the countryside near Almaty. It starts and finishes at the same point. The route is modeled as $n$ steps of equal width. Step $i$ is horizontal and sits at height $a_i$ meters above sea level. Two neighboring steps may have the same height. The difficulty of the route is the total of every climb and every descent along the closed loop.

$\text{difficulty} = |a_1 - a_2| + |a_2 - a_3| + \cdots + |a_{n-1} - a_n| + |a_n - a_1|$

The route as built is too hard for tourists. To lower the difficulty you can use $k$ blocks. A block is as wide as a step and one meter high. You can put a block on a step or on another block, and you do not have to use every block.

Find the largest possible decrease of the difficulty.

The first line contains the number of steps $n$ and the number of blocks $k$. ($2 \le n \le 10^6$, $1 \le k \le 10^9$)

The second line contains the heights $a_1, a_2, \dots, a_n$. ($0 \le a_i \le 10^9$)

Print the largest possible decrease of the difficulty on one line.

In the first example the difficulty of the route is 6: three descents of height 1, and one climb of height 3 that leads from the last step back to the first one. Putting one block on the third step and two blocks on the last step lowers the difficulty by 4. Using all five blocks gives the same answer, and no arrangement lowers the difficulty further.