题目翻译

题目描述：

快餐连锁店 McBurger 在一条高速公路上拥有多家餐厅。最近，他们决定在高速公路上建造若干个仓库，每个仓库位于某家餐厅的位置，并为多家餐厅提供所需的食材。自然，这些仓库的位置应使得餐厅与其分配的仓库之间的平均距离最小化。你需要编写一个程序来计算仓库的最佳位置和分配方案。

具体来说，McBurger 的管理层给出了以下规范：你将获得高速公路沿线 n 家餐厅的位置，用 n 个整数 ( d_1 < d_2 < \dots < d_n ) 表示（这些距离是从公司总部测量的，总部也位于同一条高速公路上）。此外，还会给出一个数字 ( k )（( k \leq n )），表示需要建造的仓库数量。

这 k 个仓库将建在 k 家不同餐厅的位置上。每家餐厅将被分配到最近的仓库，并从该仓库获取供应。为了最小化运输成本，总距离和（定义为所有餐厅到其分配的仓库的距离之和）必须尽可能小。

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

输入：

输入文件包含多个快餐连锁店的描述。每个描述的第一行包含两个整数 ( n ) 和 ( k )。( n ) 和 ( k ) 满足 ( 1 \leq n \leq 200 )，( 1 \leq k \leq 30 )，且 ( k \leq n )。接下来的 ( n ) 行每行包含一个整数，表示餐厅的位置 ( d_i )，按升序排列。

输入文件以 ( 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