Description

Paul 拥有一家餐饮公司，生意兴隆。公司有 $k$ 个餐饮团队，每个团队负责一套餐饮设备。每周，公司会接受 $n$ 个不同活动的餐饮请求。对于每个请求，他们会派遣一个餐饮团队及其设备到活动地点。团队负责送餐、安装设备，并指导主办方如何使用设备和提供餐饮。活动结束后，主办方负责将设备归还给 Paul 的公司。

不幸的是，有些周的餐饮团队数量少于请求数量，因此一些团队可能需要用于多个活动。在这种情况下，公司不能等待主办方归还设备，必须让团队留在现场以便将设备转移到另一个地点。公司可以准确估算从任何地点到任何其他地点移动一套设备的成本。鉴于这些成本，Paul 希望准备一份“高级餐饮地图”以满足请求，同时最小化设备的总移动成本（包括首次移动的成本），即使这意味着不使用所有可用的团队。Paul 需要你的帮助来编写一个程序来完成这个任务。请求按活动时间的升序排序，并且选择这些请求的方式是，对于任何 $i < j$，都有足够的时间将用于第 $i$ 个请求的设备运输到第 $j$ 个请求的地点。

Input Format

输入的第一行包含两个整数 $n$ ($1 \le n \le 100$) 和 $k$ ($1 \le k \le 100$)，分别表示请求的数量和餐饮团队的数量。接下来的 $n$ 行中，第 $i$ 行包含 $n-i+1$ 个整数，范围在 $0$ 到 $1,000,000$ 之间（包含）。第 $i$ 行的第 $j$ 个数字表示将一套设备从位置 $i$ 移动到位置 $i+j$ 的成本。公司位于位置 $1$，$n$ 个请求位于位置 $2$ 到 $n+1$。

Output Format

显示服务所有请求的最小移动成本。（此金额不包括将设备移回餐饮公司的成本。）

3 2
40 30 40
50 10
50

80

3 2
10 10 10
20 21
21

40

Hint

时间限制：4000 毫秒，内存限制：1048576 kB。

国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2015。

题面翻译由 ChatGPT-4o 提供。