Логисту нужно организовать перевозку n грузов через реку. Грузы уже выстроены в очередь, и менять их порядок нельзя. Вес i-го груза равен a_i.

За один день паром может перевезти некоторый подряд идущий отрезок очереди: он загружает грузы по порядку, пока добавление следующего груза не привело бы к превышению грузоподъёмности парома cap. На следующий день погрузка продолжается с первого неперевезённого груза.

Требуется подобрать минимальную целую грузоподъёмность парома cap, при которой все грузы можно перевезти не более чем за D дней.

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

Первая строка содержит два целых числа n и D — количество грузов и допустимое число дней.

Вторая строка содержит n целых чисел a_i — веса грузов в порядке очереди.

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

Выведите одно целое число — минимальную грузоподъёмность парома cap, достаточную для перевозки всех грузов не более чем за D дней.

Ограничения

• 1 <= D <= n <= 2 * 10^5
• 1 <= a_i <= 10^9

Примеры

Пример 1

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

5 3
1 2 3 4 5

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

6

Пример 2

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

6 1
7 1 9 2 8 3

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

30