题目描述

皮皮是一名忠实的游戏爱好者，最近他迷上了一款叫作《怪物猎人》的动作角色扮演游戏。游戏的内容很简单，只要不停地制造武器打怪就好了。

这个游戏一共有 N 个怪物，分别有着不同的等级。皮皮需要在 K 天内按顺序把它们都打败。每一天，皮皮要做的第一件事情就是打造一把武器，而武器也有对应的等级，如果武器的等级低于怪物，那么皮皮就打不过那个怪物，否则皮皮就能战胜它。

已知皮皮每天只会去一次武器铺，购买任意等级的武器，然后去打一整天的怪物。但是每用一个武器打败一个怪物后，就需要支付与武器等级同样的金币来修理武器，注意：即使是击杀最后一个怪物也需要修理武器。

现在皮皮已经知道了 N 个怪物的等级，他想知道自己最少需要花费多少枚金币，能在 K 天内击杀所有的怪物。

输入格式

输入第一行两个整数 N 和 K，表示有 N 个怪物，皮皮有 K 天时间打怪。

第二行 N 个整数，依次表示 1∼N 号怪物的等级 $T_i$。

输出格式

输出一个正整数，表示皮皮至少需要花费的金币数。

样例输入

6 3
6 9 8 2 3 2

样例输出

33

提示

对于 20% 数据，$K=2$；

对于 50% 数据，$1\le K\le 10,1\le N\le 30$；

对于 100% 数据，$1\le K\le N\le 500,0\le T_i\le 10^{5}$。

样例 1 说明

第一天打 1 号怪，花费 6 金币；

第二天打 2、3 号怪，花费 $9\times 2=18$ 金币；

第三天打 4∼6 号怪，花费 $3\times 3=9$金币。共花费 33 金币。

6 3
6 9 8 2 3 2

33

6 3 
6 9 8 2 3 2

33

6 3  
6 9 8 2 3 2

33