题目描述

在一个美丽的秋天，丽丽每天都经过的花园小巷落满了树叶，她决定把树叶堆成 \(k\) 堆，小巷是笔直的，共有 \(n\) 片树叶（树叶排列也是笔直的），每片树叶都有一个重量值，并且每两片相邻的树叶之间的距离都是 \(1\)。现把所有的树叶按从左到右的顺序进行编号，编号为 \(1\sim n\)。丽丽移动每片树叶所消耗能量等于这片树叶的重量乘以移动的距离，丽丽决定分 \(k\) 天完成，每天堆一堆，并且规定只能把树叶往左移动，因为丽丽每天都是从右往左经过小巷的。求丽丽完成任务所消耗的最少能量。

格式

输入格式

第一行：两个用空格隔开的正整数： \(n\) 和 \(k\)。

下面 \(n\) 行：每行一个正整数，表示叶子的重量（第 \(i+1\) 行表示第 \(i\) 片树叶的重量）

输出格式

第一行：一个整数，表示把树叶堆成 \(k\) 堆所消耗的最少体力。

样例1

输入样例1

5 2 
1
2
3
4
5

输出样例1

13

样例解释

最理想的堆法是分别堆在 \(1\) 和 \(4\) 的位置，把树叶\(1, 2\) 和 \(3\) 移动到位置 \(1\)，把树叶 \(4\) 和 \(5\) 移动到位置 \(4\)。 总价值为： \(1 \times 0 + 2 \times 1 + 3 \times 2 + 4 \times 0 + 5 \times 1 = 13\)。

限制

\(100\%\)的数据：\(1≤ K ≤20,1≤ N ≤1000\)。