该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

【问题描述】

操场的一侧有 N 个石子排成一排，按顺时针方向从左到右编号为 1 ~ N，其中第 i 个石子的重量为 Wi，相邻两个石子的距离都是 1。

小 A 正准备绕着操场跑圈。他刚学完区间 dp 的石子合并问题，看到操场边上的石子，他突然蹦出了一个想法：要把所有石子合并成恰好 K 堆。

他打算这样来完成这个任务：

1、他要逆时针恰好跑 K 圈，每一圈在经过石子时，顺便（必须）完成一次合并，即将若干个（至少两个，不一定连续）石子合并成一堆。

2、每次合并过程都是沿着他的跑步方向，也就是从右到左进行合并，只能将右边的若干个石子向左移动，移动每个石子的代价是这个石子的重量乘以它移动的距离。

求完成任务的最小总代价？

【输入格式】

第一行为两个整数 N, K。

接下来 N 行，每行一个正整数 Wi

【输出格式】

一个整数，表示最小总代价。

【样例输入】

5 2
1
2
3
4
5

【样例输出】

13

【样例解释】

第一次合并，将 5 号石子移动到 4 号位置，代价为 5 × 1 = 5；

第二次合并，将 3 号石子和 2 号石子移动到 1 号位置，代价为 3 × 2 + 2 × 1 = 8；

这样最终在 1 号位置和 4 号位置共有 2 堆石子。

总代价为 5 + 8 = 13。

除此之外，找不到其他总代价更小的合并方案。

【数据范围】

20% 的数据：1 ≤ N ≤100, 1 ≤ K ≤ 5

100% 的数据：1 ≤ N, Wi ≤1000, 1 ≤ K ≤ 10