Farmer John은 놀라운 회계 천재로 농장 운영 자금이 바닥날 수 있음을 깨달았습니다. 다음 $N$일($1 \le N \le 100,000$) 동안 매일 필요한 정확한 지출($1 \le money_{i} \le 10,000$)을 계산해 기록했습니다.

FJ는 “fajomonths”라 부르는 연속된 정확히 $M$개 회계 기간($1 \le M \le N$)에 예산을 세웁니다. 기간마다 하루 이상 연속된 날을 포함하고, 매일은 정확히 한 기간에 속합니다.

지출이 가장 큰 기간의 지출을 최소화하도록 기간을 나눠 월별 지출 한도를 정합니다.

입력

줄 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년 3월.