화물 열차에 실어야 할 \(N\)개의 화물이 순서대로 놓여 있다. 각 화물의 무게는 서로 다를 수도 있다.

화물을 열차에 실을 때에는 다음 조건을 지켜야 한다.

• 모든 화물을 \(M\)개의 화물칸에 나누어 실어야 한다.
• 화물이 놓인 순서를 바꿀 수 없다.
• 하나의 화물을 여러 화물칸에 나누어 실을 수 없다.
• 같은 화물칸에 두 화물을 실었다면, 두 화물 사이에 놓인 모든 화물도 같은 화물칸에 실어야 한다.
• 모든 화물칸의 적재 한도는 같다.

각 화물의 무게가 주어질 때, 모든 화물을 실을 수 있는 화물칸 적재 한도의 최솟값을 구하여라.

입력

첫째 줄에 화물의 수 \(N\)과 화물칸의 수 \(M\)이 공백으로 구분되어 주어진다.

둘째 줄에 \(N\)개 화물의 무게가 놓인 순서대로 주어진다.

출력

모든 화물을 조건에 맞게 실을 수 있는 화물칸 적재 한도의 최솟값을 출력한다.

제한 사항

• \(1 \le N \le 100,000\)
• \(1 \le M \le N\)
• 각 화물의 무게는 \(1\) 이상 \(10,000\) 이하의 자연수이다.

예제 입력 1

7 3
4 2 7 3 6 5 2

예제 출력 1

13

예제 설명 1

화물을 다음과 같이 세 화물칸에 나누어 실을 수 있다.

• 첫 번째 화물칸: \(4, 2, 7\) — 총무게 \(13\)
• 두 번째 화물칸: \(3, 6\) — 총무게 \(9\)
• 세 번째 화물칸: \(5, 2\) — 총무게 \(7\)

따라서 적재 한도가 \(13\)이면 모든 화물을 실을 수 있다.

적재 한도가 \(12\)라면 첫 번째 화물칸에는 \(4, 2\)까지, 두 번째 화물칸에는 \(7, 3\)까지, 세 번째 화물칸에는 \(6, 5\)까지 실을 수 있다. 이 경우 마지막 화물 \(2\)를 실을 화물칸이 하나 더 필요하다.

따라서 가능한 적재 한도의 최솟값은 \(13\)이다.

예제 입력 2

5 2
8 1 1 1 8

예제 출력 2

10