| Codeforces Round 466 (Div. 2) |
|---|
| Закончено |
Вам, как лучшему Врейс-Кингу, в нижнем магазине «Мир» в центре Винницы предлагаются скидки.
Дан массив a длины n и целое число c.
Стоимость массива b длины k это сумма его элементов, за исключением 
минимальных. Например, стоимость массива [3, 1, 6, 5, 2] при c = 2 это 3 + 6 + 5 = 14.
Среди всех разбиений a на последовательные подмассивы, найдите минимально возможную сумму стоимостей этих подмассивов.
В первой строке находится два числа n и c (1 ≤ n, c ≤ 100 000).
Следующая строка содержит n чисел ai (1 ≤ ai ≤ 109) — элементы массива a.
Выведите единственное число — минимально возможную сумму стоимостей подмассивов некого разбиения a.
3 5
1 2 3
6
12 10
1 1 10 10 10 10 10 10 9 10 10 10
92
7 2
2 3 6 4 5 7 1
17
8 4
1 3 4 5 5 3 4 1
23
В первом примере любое разбиение на подмассивы даст сумму 6.
Во втором тестовом примере одним из оптимальных разбиений является [1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10] со стоимостями 2 и 90 соответственно.
В третьем тестовом примере одним из оптимальных разбиений является [2, 3], [6, 4, 5, 7], [1] со стоимостями 3, 13 и 1 соответственно.
В четвертом тестовом примере одним из оптимальных разбиений является [1], [3, 4, 5, 5, 3, 4], [1] со стоимостями 1, 21 и 1 соответственно.
