Задан массив из n элементов и число k. Разбейте заданный массив на k подмассивов (которые содержат в себе все элементы). Вычислим максимум среди сумм элементов всех k подмассивов. Разбиение следует провести так, чтобы это значение было как можно меньшим. Найдите этот максимум.

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

Первая строка содержит два числа n и k (n ≤ 106, 1 ≤ k ≤ n). Вторая строка содержит n натуральных чисел, каждое из которых не более 109.

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

Выведите наименьшее возможное значение среди максимумов сумм элементов всех k подмассивов.

Пояснение

Для первого примера оптимальным разбиением будет {1, 2}, {3}, {4}. Максимум сумм элементов среди всех подмассивов равен 4, который является наименьшим возможным для 3 подмассивов.

Для второго примера оптимальным разбиением будет {1, 2, 3, 4}, {2, 3, 4}, {2, 3, 1}. Максимум сумм элементов среди всех подмассивов равен 10, который является наименьшим возможным для 3 подмассивов.