추정

"여기 숫자가 너무 많잖아!" 상사가 소리칩니다. "이걸 어떻게 다 이해하라는 거야? 줄여! 추정해!"

애써 만든 숫자들이라 아쉽지만, 상사가 시키는 대로 하기로 합니다.

추정은 다음과 같이 합니다. 크기가 $n$인 수열 $A$가 주어지면, 이를 연속한 $k$개의 구간으로 나눕니다. 각 구간의 크기가 서로 같을 필요는 없습니다. 그런 다음 각 구간 전체를 하나의 수로 추정합니다. 즉, 크기가 $n$인 수열 $A$로부터 크기가 $n$인 또 다른 수열 $B$를 만드는데, $B$는 연속한 $k$개의 구간으로 이루어지며 두 인덱스 $i$와 $j$가 같은 구간에 속하면 $B[i] = B[j]$입니다. 목표는 오차, 즉 절댓값 차이의 합 $\sum |A[i] - B[i]|$를 최소화하는 것입니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$ ($1 \le n \le 2000$)과 $k$ ($1 \le k \le 25$, $k \le n$)가 주어지며, $n$은 수열의 크기이고 $k$는 추정에 사용할 연속 구간의 개수입니다. 이어지는 $n$개의 줄에는 각각 $A$의 정수 원소가 하나씩 주어지며, 모든 원소는 $-10000 \le A[i] \le 10000$을 만족합니다. 입력의 마지막 줄에는 두 개의 0이 주어집니다.

각 테스트 케이스마다 한 줄에 정수 하나, 곧 달성할 수 있는 최소 오차를 출력합니다. 불필요한 공백을 출력하지 말고, 답과 답 사이에 빈 줄을 넣지 마십시오. 모든 답은 부호 있는 64비트 정수에 들어갑니다.