问题描述

高桥君决定将 $N$ 只小鸡分配到 $M$ 个鸟笼中。每只小鸡都有一个从 $1$ 到 $N$ 的编号，小鸡 $i$ 的大小为 $A_i$。

由于鸟笼空间有限，每只小鸡都会受到与其所在鸟笼中所有小鸡大小之和（包括它自己）相等的压力。

请计算小鸡受到的压力总和的最小值。

约束条件

• $1 \leq M \leq N \leq 2{,}000$
• $1 \leq A_i \leq 10^9$
• 输入数据都为整数

输入

输入数据从标准输入中按如下格式给出。

$N$ $M$ $A_1$ $A_2$ $...$ $A_{N}$

输出

输出答案。

示例 1

5 3
3 6 2 15 9

输出示例 1

55

• 当将小鸡放入鸟笼 $(1,2),(3,5),(4)$ 中时，受到的压力总和为 $9+9+11+15+11 = 55$，这是最小值。

示例 2

13 4
4 3 9 1 3 8 2 6 11 9 2 15 40

输出示例 2

304

示例 3

4 2
1000000000 1000000000 1000000000 1000000000

输出示例 3

8000000000

请注意答案可能很大。