Горная трасса
Горная трасса
В окрестностях Алматы оборудован туристический горный круговой маршрут (старт и финиш находятся в одной точке). Будем моделировать этот маршрут n ступеньками одинаковой ширины, задавая каждую i-ю ступеньку ее высотой над уровнем моря ai
в метрах. Соседние ступеньки могут иметь одинаковую высоту. Сложность трассы определяется суммарным значением спусков и подъемов. Или формально,
difficulty = |a1
- a2
| + |a2
- a3
| + ... + |an-1
- an
| + |an
- a1
|
Оказалось, что первоначально сконструированная трасса слишком сложна для туристов. Для того чтобы ее упростить, мы можем использовать k блоков. Ширина каждого блока совпадает с шириной ступеньки, а высота равна 1 метру. Любой из блоков можно положить на любую ступеньку или ранее положенный блок или не использовать совсем.
На сколько таким образом можно уменьшить сложность трассы в целом?
Входные данные
В первой строке находятся числа n (2 ≤ n ≤ 106
) и k (1 ≤ k ≤ 109
). В следующей строке находятся n целых неотрицательных чисел - высоты каждой из ступенек.
Выходные данные
Запишите одно число - максимально возможное уменьшение сложности трассы.
4 5 4 3 2 1
4
3 2 1 2 1
2
7 1000 4 3 3 2 3 2 1
8