지원 요청 묶음의 작업 한도

문제

한 회사의 사내 IT 지원팀에는 처리할 요청 N개가 접수되어 있다. 각 요청에는 접수 순서에 따라 1번부터 N번까지 번호가 붙어 있고, 담당자가 예상한 작업량이 양의 정수로 기록되어 있다. 지원팀은 요청을 여러 묶음으로 나누어 처리하려고 한다. 앞선 요청의 처리 결과를 뒤의 요청에서 참고할 수 있으므로, 요청의 순서를 바꾸거나 다른 묶음의 요청을 사이에 끼워 넣을 수는 없다. 하나의 묶음은 원래 요청 목록에서 연속한 하나 이상의 요청으로 구성된다. 모든 요청은 정확히 하나의 묶음에 포함되어야 하며, 요청 하나를 여러 묶음으로 나누는 것은 허용하지 않는다. 따라서 묶음들은 원래 목록을 앞에서부터 빈틈없이 나눈 결과여야 한다. 묶음의 작업량은 그 안에 포함된 모든 요청의 작업량을 더한 값이다. 요청 사이의 전환 비용이나 묶음을 새로 만드는 데 드는 추가 작업량은 없다고 가정한다. 지원팀이 사용할 수 있는 처리 회차는 최대 M번이며, 한 회차에 하나의 묶음을 처리한다. 반드시 M개의 묶음을 만들 필요는 없고, 1개 이상 M개 이하의 묶음으로 나누면 된다. 모든 회차에는 공통으로 적용되는 정수 작업 한도 C가 있다. 각 묶음의 작업량이 C 이하여야 하므로, 요청 목록을 어떻게 나누는지에 따라 필요한 작업 한도가 달라질 수 있다. 팀장은 최대 M개의 묶음으로 모든 요청을 처리할 수 있도록 하는 가장 작은 작업 한도를 정하려고 한다. 예를 들어 작업량이 2, 5, 3인 세 요청을 최대 두 묶음으로 처리한다면, 앞의 두 요청을 묶고 마지막 요청을 따로 두어 한도 7로 처리할 수 있다. 한도는 각 요청의 작업량보다 작을 수 없으며, 모든 요청을 한 묶음으로 처리하는 한도는 언제나 가능하다. 묶음을 나누는 방법이 여러 개여도 방법 자체는 출력하지 않는다. 주어진 요청 작업량과 회차 제한에 대해 가능한 최소 정수 C를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 M이 공백으로 구분되어 주어진다. 1≤N≤50,000, 1≤M≤N이다.
둘째 줄에 접수 순서대로 요청 작업량 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 A_i는 1 이상 100 이하의 정수다.

출력

모든 요청을 1개 이상 M개 이하의 연속한 묶음으로 나눌 수 있는 최소 정수 작업 한도 C를 출력한다. 주어진 제약에서는 항상 답이 존재한다.

5 3
4 2 7 3 5

8

4 1
3 1 4 2

10

4 4
8 2 6 3

8

출처: Devin.KR 자체 제작