Description

某国情报部门给每个车站都分配了一个战略重要性：从$1$到$1$$0$$0$的整数。

单个车站自身没有价值，与其他车站相连才有价值。

整个铁路的战略价值是将铁路线直接或间接连接的每对车站的战略价值的乘积相加来计算的。

假设铁路如下图所示，则其战略价值为$4$×$5$+$4$×$1$+$4$×$2$+$5$×$1$+$5$×$2$+$1$×$2$$=$$4$$9$。

假设只有一次攻击，不可以攻击车站，只能攻击两个车站之间的铁路线。

若攻击了中间的这条铁路线，则剩余铁路的战略价值为$4$×$5$+$1$×$2$$=$$2$$2$。

但是，假设攻击了$4$和$5$之间的铁路线，则剩余铁路的战略价值为$5$×$1$+$5$×$2$+$1$×$2$$=$$1$$7$。

给出一条铁路的描述和可以执行的攻击次数，找出可以实现的最小战略价值。

Format

Input

输入包含几个测试用例。

每个测试用例都以两个整数$n$$（$$1$$≤$$n$$≤$$1$$0$$0$$0$$）$和$m$$（$$0$$≤$$m$$<$$n$$）$为开头。

$n$是铁路上的站点数量，$m$是攻击数量。

下一行是$n$个整数，范围为$1$～$1$$0$$0$，依次表示每个站点的战略价值。

输入以两个$0$结束。

Output

对每个测试用例，都单行输出通过攻击可以实现的铁路的最小战略值。

Samples

4 1
4 5 1 2
4 2
4 5 1 2
0 0

17
2