Разделение массива с минимальной суммой

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

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

Первая строка входных данных содержит два целых числа n (1 ≤ n ≤ ) и k (1 ≤ k ≤ n).

В следующей строке заданы через пробел целые числа ( ≤ ≤ ).

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

Необходимо вывести минимально возможное значение максимальной суммы среди выбранных подмассивов.

Примеры

Пояснение

1. [1 2 3] [6 2] ⇒ максимальная сумма подмассива: 6 + 2 = 8

2. [1 2] [10] [3 2] ⇒ максимальная сумма подмассива: 10