패스트푸드

패스트푸드 체인 McBurger는 고속도로를 따라 여러 개의 음식점을 운영하고 있으며, 그중 일부 음식점의 위치에 물류 창고를 지어 나머지 음식점에 재료를 공급하려고 한다. 창고는 각 음식점과 그 음식점이 배정된 창고 사이의 거리 합이 최소가 되도록 배치해야 한다.

고속도로 위 $n$개 음식점의 위치가 정수 $d_1 < d_2 < \dots < d_n$로 주어진다(같은 고속도로 위의 한 기준점으로부터의 거리이다). 또한 지을 창고의 개수 $k$ ($k \le n$)가 주어진다.

$k$개의 창고는 서로 다른 $k$개 음식점의 위치에 지어지며, 각 음식점은 가장 가까운 창고에 배정된다. 이때 전체 거리 합

$$\sum_{i=1}^{n} \left| d_i - p(i) \right|$$

을 최소로 만들어야 한다. 여기서 $p(i)$는 음식점 $i$를 담당하는 창고의 위치이다. 가능한 최소 전체 거리 합을 구하여라.

입력은 여러 개의 체인에 대한 정보를 담고 있다. 각 체인은 두 정수 $n$과 $k$가 적힌 줄로 시작하며, $1 \le n \le 200$, $1 \le k \le 30$, $k \le n$을 만족한다. 이어지는 $n$개의 줄에는 음식점의 위치 $d_i$가 오름차순으로 한 줄에 하나씩 주어진다.

입력의 끝은 첫 줄이 0 0인 체인으로 표시되며, 이 체인은 처리하지 않는다.

각 체인에 대해 주어진 순서대로 Chain i: S 형식의 한 줄을 출력한다. 여기서 i는 체인의 1부터 시작하는 번호이고, S는 가능한 최소 전체 거리 합이다. 끝을 나타내는 0 0 체인은 아무것도 출력하지 않는다.