택배 트럭 \(K\)대에 \(N\)개의 상자를 실으려 한다. 상자는 컴베이어에 놓인 순서를 바꿀 수 없으며, 각 트럭은 연속한 구간의 상자들을 실는다. 즉 상자들을 순서를 유지한 채 \(K\)개의 연속 구간으로 나누어 각 구간을 한 트럭이 담당한다.

어떤 트럭이 실는 상자 무게의 합을 그 트럭의 적재량이라 할 때, 가장 무거운 트럭의 적재량을 최소로 하고 싶다. 이때 가능한 최소 적재량을 출력하여라.

• \(1 \le K \le N \le 100\,000\)
• 각 상자의 무게는 \(1\) 이상 \(10\,000\) 이하

첫째 줄에 상자의 수 \(N\)과 트럭의 수 \(K\)가 공백으로 구분되어 주어진다.

둘째 줄에 \(N\)개의 상자 무게가 컴베이어 순서대로 공백으로 구분되어 주어진다.

가장 무거운 트럭의 최소 적재량을 한 줄에 출력한다.

riseoj 작성

출처 Original