题目描述

一只公羊是一名程序员。它正在运行若干模拟，用来研究攻城槌如何撞毁城墙。

它总共要在“云端”运行 N 个模拟。每个模拟都恰好需要 1 分钟 的计算时间，但所需内存不同。第 i 个模拟需要的内存为 R_i MB。

公羊必须把这 N 个模拟划分成恰好 K 个“任务”提交到云端。对于同一个任务中的模拟：

• 它们按顺序依次运行；
• 因此该任务总共需要的时间，等于这个任务中模拟的数量；
• 该任务需要预留的内存，等于其中所有模拟所需内存的最大值。

云服务的收费单位是MB·分钟。因此，一个任务的费用等于：

• 任务运行的分钟数
• 乘以
• 该任务需要预留的内存（MB）

公羊希望最小化所有任务费用之和。

请你编写程序 ram.cpp，求出最小可能的总费用。

输入格式

第一行输入两个整数 N 和 K。
第二行输入 N 个整数：R_0, R_1, ..., R_{N-1}。

输出格式

输出一行一个整数，表示最小可能的总 MB·分钟。

数据范围

• 1 <= K <= N <= 10^6
• 0 <= R_i <= 10^{12}

子任务

要获得某个子任务的分数，你的程序必须通过该子任务及之前所有子任务中的所有测试。

样例

输入

10 4
4 1 12 17 7 3 6 8 10 16

输出

94

样例解释

一种最优划分方式如下：

1. 4, 1, 3：3 × max(4,1,3) = 12
2. 12, 10：2 × max(12,10) = 24
3. 7, 6, 8：3 × max(7,6,8) = 24
4. 17, 16：2 × max(17,16) = 34

总费用为：

12 + 24 + 24 + 34 = 94