В окрестностях Алматы оборудован туристический горный круговой маршрут (старт и финиш находятся в одной точке). Будем моделировать этот маршрут n ступеньками одинаковой ширины, задавая каждую i-ю ступеньку ее высотой над уровнем моря ai в метрах. Соседние ступеньки могут иметь одинаковую высоту. Сложность трассы определяется суммарным значением спусков и подъемов. Или формально,

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

Оказалось, что первоначально сконструированная трасса слишком сложна для туристов. Для того чтобы ее упростить, мы можем использовать k блоков. Ширина каждого блока совпадает с шириной ступеньки, а высота равна 1 метру. Любой из блоков можно положить на любую ступеньку или ранее положенный блок или не использовать совсем.

На сколько таким образом можно уменьшить сложность трассы в целом?

Входные данные

В первой строке находятся числа n (2 ≤ n ≤ 106) и k (1 ≤ k ≤ 109). В следующей строке находятся n целых неотрицательных чисел - высоты каждой из ступенек.

Выходные данные

Запишите одно число - максимально возможное уменьшение сложности трассы.