공장 설비 개선

공장 계획 위원회의 일원으로서 생산 과정을 감독하고 모든 작업이 원활하게 돌아가도록 책임진다.

위원회는 생산 라인의 기계가 고장 없이 상자를 처리하기를 원한다. 기계는 무거운 물건을 다룰 때 고장이 나기 쉬우므로, 위원회는 기계마다 최대 무게 용량을 정하자고 제안한다. 예산 문제로 위원회는 기계를 시작할 수 있는 횟수도 최대 $k$번으로 제한하기로 했다.

여러분의 과제는 기계 라인을 최대 $k$번 시작하고, 상자를 주어진 순서대로 모두 처리할 수 있는 최소 무게 용량을 구하는 것이다.

예를 들어 상자를 다음 세 개의 연속된 구간으로 나눌 수 있다.

$\{7\}, \{3, 2, 3\}, \{1, 4\}$

이렇게 나누면 기계의 용량은 8이면 된다.

입력은 다음과 같다.

• 첫 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \leq n \leq 10^5$, $1 \leq k \leq 10^3$). $n$은 상자의 개수이고, $k$는 기계를 시작할 수 있는 횟수이다.
• 둘째 줄에 $n$개의 정수 $x$가 주어진다 ($1 \leq x \leq 10^{10}$). 이는 상자의 무게이며, 처리해야 하는 순서대로 나열되어 있다.

기계를 $k$번 이하로 실행해 모든 상자를 처리하는 데 필요한 최소 무게 용량을 출력한다.