In Almaty countryside a mountain cycle trek route (a route with a start and finish at one point) has been constructed. We will simulate the route in a way of stairs (not hills) of one and the same width each, each step i is horizontal and is marked by the sea level ai meters. Hegths of neighbor stairs may be equal. The difficulty of the route is a sum of ups and downs. More formaly

difficulty = |a1 - a2| + |a2 - a3| + ... + |an-1 - an| + |an - a1|

The first constructed trek route appeared to be too challenging for tourists. To decrease the route difficulty we can use k blocks. The block's width equals stair's width and the block's height equals one meter. We may put any block on any stair or on another block or does't use it at all. Dene the maximum possible decrease of the trek route difficulty.

Input

In the first line there are the following numbers n (2 ≤ n ≤ 106) and k (1 ≤ k ≤ 109). In the next line there are n non-negative integers which are the height of each of the stairs.

Output

Output one number, which is maximum possible decrease of the trek route difficulty.