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

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

В первой строке находятся два целых числа n и k (1 ≤ n ≤ 105, 1 ≤ k ≤ min(n, 100)). В следующей строке заданы n целых чисел A1, A2, ..., An (1 ≤ Ai ≤ 106) - элементы последовательности.

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

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