Paul 拥有一家餐饮公司，生意非常兴隆。该公司拥有 $k$ 个餐饮团队，每个团队负责一套餐饮设备。每周，公司会收到 $n$ 个餐饮服务请求。对于每个请求，他们都会派遣一个餐饮团队携带设备前往活动地点。团队负责运送食物、布置设备，并指导主办方如何使用设备和供应食物。活动结束后，主办方负责将设备归还给 Paul 的公司。

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

输入格式

输入的第一行包含两个整数 $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$。

输出格式

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

样例

输入 1

3 2
40 30 40
50 10
50

输出 1

80

输入 2

3 2
10 10 10
20 21
21

输出 2

40