기타 레슨

한 강사가 기타 강의 동영상을 여러 장의 블루레이에 순서대로 담아 판매하려고 한다. 강의는 모두 번호 순서대로 녹화되어야 하며, 순서가 바뀌면 강의 흐름이 끊긴다. 따라서 i번째 강의와 j번째 강의가 같은 블루레이에 들어간다면, 그 사이에 있는 모든 강의도 같은 블루레이에 들어가야 한다.

강사는 모든 강의를 정확히 M장의 블루레이에 담기로 했다. 모든 블루레이의 용량은 같아야 하며, 각 강의는 하나의 블루레이에 통째로 들어가야 한다. 가능한 블루레이 용량 중 최솟값을 구하시오.

첫째 줄에 강의의 수 N과 블루레이의 수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

둘째 줄에는 각 강의의 길이가 강의 순서대로 분 단위의 자연수로 주어진다. 각 강의의 길이는 10,000분 이하이다.

가능한 블루레이 용량의 최솟값을 첫째 줄에 출력한다.

강의가 9개이고 블루레이가 3장인 경우를 생각해 보자. 1번 블루레이에 1번부터 5번 강의를, 2번 블루레이에 6번과 7번 강의를, 3번 블루레이에 8번과 9번 강의를 넣으면 각 블루레이에 담긴 강의 길이의 합은 15, 13, 17이 된다. 모든 블루레이의 용량이 같아야 하므로 필요한 용량은 17이며, 이보다 작은 용량으로는 모든 강의를 담을 수 없다.