K개의 블록

양의 정수 $N$개로 이루어진 수열 $A$가 주어진다. 이 수열을 정확히 $K$개의 블록으로 나눈다. 블록은 연속한 원소로 이루어지고 비어 있지 않으며, 모든 원소는 정확히 한 블록에 속한다.

분할의 값은 $K$개의 블록에서 각각 가장 큰 원소를 골라 모두 더한 값이다. 주어진 $K$에 대해 분할의 값이 될 수 있는 최솟값을 구하라.

첫째 줄에 두 정수 $N$과 $K$가 주어진다 ($1 \le K \le N \le 2000$).

둘째 줄에 수열의 원소 $A_1, A_2, \ldots, A_N$이 주어진다 ($1 \le A_i \le 10^6$).

$K$개의 블록으로 나눈 분할의 값 중 최솟값을 한 줄에 출력한다.