Гірська траса
У передмісті Алмати створено туристичний гірський круговий маршрут, де старт і фініш збігаються в одній точці. Цей маршрут можна уявити як n рядків однакової ширини, де кожен i-й рядок має висоту над рівнем моря a[i] у метрах. Сусідні рядки можуть бути на одній висоті. Складність маршруту визначається сумарною величиною спусків і підйомів, що обчислюється за формулою:
difficulty = |a[1] - a[2]| + |a[2] - a[3]| + ... + |a[n-1] - a[n]| + |a[n] - a[1]|
З'ясувалося, що початковий маршрут виявився занадто складним для туристів. Щоб його спростити, можна використати k блоків. Кожен блок має таку ж ширину, як і рядок, а його висота становить 1 метр. Будь-який блок можна розмістити на будь-якому рядку або на вже розміщеному блоці, або не використовувати взагалі.
Яким чином можна максимально зменшити складність маршруту?
Вхідні дані
Перший рядок містить числа n (2 ≤ n ≤ 10^6) і k (1 ≤ k ≤ 10^9). У наступному рядку наведено n цілих невід'ємних чисел, що представляють висоти кожного з рядків.
Вихідні дані
Виведіть одне число - максимально можливе зменшення складності маршруту.