更确切的说，我们会给你n个整数，分别表示n个餐馆的位置坐标（沿着公路，假设公路为直线）。然后还会给你一个整数k (k ≤ n)表示仓库的数目。

　　这k个仓库会修在k个不同的餐馆处，每个餐馆分配离它最近的仓库。总的距离和定义如下：

　　　　　　　　　　

　　写一个程序计算出仓库的位置，使得上述距离总和最小。

　　输入

　　输入文件包含很多段，每一段是很多行。除了最后一段外，每一段都定义了一些餐馆的位置以及仓库的个数。每一段的第一行是两个整数n和k，分别满足1≤n≤200,1≤k≤30,k≤n。接下来是n行，每行一个整数，顺序的表示餐馆的位置。

　　最后一段只包含n=k=0，这段不用处理。

　　输出

　　对于每个段，首先输出号码，接着以如下方式输出仓库的位置：对于每个仓库用一行输出它的位置和它供给的餐馆编号。如果有多于一个的最优解，只需输出其中任何一个。最后用一行输出总的距离和。

　　每个段后输出一个空行。

　　例

　　输入文件：
　　6 3
　　5
　　6
　　12
　　19
　　20
　　27
　　0 0

　　输出文件：
　　Chain 1
　　Depot 1 at restaurant 2 serves restaurants 1 to 3
　　Depot 2 at restaurant 4 serves restaurants 4 to 5
　　Depot 3 at restaurant 6 serves restaurant 6
　　Total distance sum = 8