Farmer John — удивительный мастер бухгалтерии; он понял, что деньги на ферму могут закончиться. Он точно рассчитал и записал расходы ($1 \le money_{i} \le 10,000$) на каждый из следующих $N$ дней ($1 \le N \le 100,000$).

FJ составляет бюджет для ровно $M$ последовательных финансовых периодов ($1 \le M \le N$), называемых «fajomonths». Каждый содержит один или несколько последовательных дней, каждый день входит ровно в один период.

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

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

Строка 1: два целых $N$ и $M$ через пробел. Строки $2\ldots N+1$: строка $i+1$ содержит расходы Farmer John в долларах на день $i$.

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

Строка 1: наименьший возможный месячный лимит Farmer John.

Примеры

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

7 5
100
400
300
100
500
101
400

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

500

Примечание

Если первые два дня составят месяц, третий и четвёртый — месяц, а последние три — каждый отдельный месяц, расходы не превысят 500 долларов в месяц. Любое другое разбиение даёт больший минимальный месячный лимит.

Источник задачи: USACO, март 2007.