K блоков

Вам дана последовательность A из n целых положительных чисел. Назовем значением разбиения последовательности на k блоков, сумму максимумов в каждом из k блоков. Вам нужно по заданному числу k найти величину разбиения с минимальным значением.

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

В первой строке находятся два целых числа n и k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ min(n, 100)). В следующей строке заданы n целых чисел A[1], A[2], ..., A[n] (1 ≤ A[i] ≤ 10^6) - элементы последовательности.

Выведите единственное число - значение минимального разбиения.

Примеры