题目描述

达尔文正在研究若干只螃蟹。现在他有 N 只螃蟹，并且已经按照某种标准将它们排成了固定顺序 1..N。第 i 只螃蟹的攻击性为 A_i，且 A_i > 0。

达尔文有 K 个水族箱，准备把这些螃蟹依次分到这些水族箱中。为了尽量不打乱原顺序，他决定采用如下分配方式：

• 前 T_1 只放进第一个水族箱；
• 接着 T_2 只放进第二个水族箱；
• …
• 最后 T_K 只放进第 K 个水族箱。

其中：

并且每个 T_i 都是非负整数。

螃蟹之间会产生“恐惧感”。如果两只螃蟹被放在同一个水族箱中，那么螃蟹 i 对于另一只螃蟹 j 的恐惧值等于 A_j。因此，螃蟹 i 的总恐惧值，等于与它同箱的所有其他螃蟹攻击性之和。

达尔文希望选择一种划分方案，使得 所有螃蟹总恐惧值之和最小。

请你求出这个最小值。

输入格式

第一行输入两个正整数 N, K，表示螃蟹数量和水族箱数量。

第二行输入 N 个正整数 A_1, A_2, ..., A_N，表示每只螃蟹的攻击性。

输出格式

输出一行一个非负整数，表示最小可能的总恐惧值。

数据范围

• 1 <= K <= N <= 10^5
• 1 <= A_i <= 10^7

子任务与评分

样例 #1

输入 #1

8 4
8 1 2 3 9 1 9 1

输出 #1

32

样例 #2

输入 #2

6 3
10 3 8 5 4 7

输出 #2

37

说明

对于样例 1，一种最优划分为：

• 第 1 只螃蟹单独放在第 1 个水族箱；
• 第 2~4 只放在第 2 个水族箱；
• 第 5~6 只放在第 3 个水族箱；
• 第 7~8 只放在第 4 个水族箱。

此时各螃蟹恐惧值分别为：

0, 5, 4, 3, 1, 9, 1, 9

总和为：

32