Бригадиру нужно распределить работу по покраске длинной ленты между k малярами. Лента состоит из n подряд идущих участков, для каждого участка известен объём работы a_i.

Требуется разбить ленту на k непустых подряд идущих отрезков, по одному отрезку на каждого маляра. Нагрузка маляра равна сумме объёмов работы на участках его отрезка.

Бригадир хочет организовать распределение так, чтобы нагрузка самого загруженного маляра была как можно меньше.

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

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

Первая строка содержит два целых числа n и k — количество участков ленты и количество маляров (1 <= k <= n <= 2 * 10^5).

Вторая строка содержит n целых чисел a_i — объёмы работы на участках (0 <= a_i <= 10^9).

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

Выведите одно число — минимально возможную максимальную нагрузку маляра.

Ограничения

• 1 <= k <= n <= 2 * 10^5
• 0 <= a_i <= 10^9
• Каждый маляр должен получить ровно один непустой подряд идущий отрезок ленты
• Все участки ленты должны быть распределены между малярами без пропусков и пересечений

Примеры

Пример 1

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

1 1
5

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

5

Пример 2

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

6 6
1 0 3 0 5 0

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

5