题目描述

有 $n$ 堆石头排成一排，第 $i$ 堆中有 $stones[i]$ 块石头。

每次 移动 需要将 连续的 $k$ 堆石头合并为一堆，而这次移动的成本为这 $k$ 堆中石头的总数。

返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 $-1$ 。

输入格式

第一行两个空格分开的整数 $n, k$；

第二行 $n$ 个空格分隔的整数表示数组 $stones$ 中的各个元素。

输出格式

把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 $-1$ 。

示例 1：

4 2
3 2 4 1

20

解释:

从 [3, 2, 4, 1] 开始。

合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。

合并 [4, 1]，成本为 5，剩下 [5, 5]。

合并 [5, 5]，成本为 10，剩下 [10]。

总成本 20，这是可能的最小值。

示例 2：

4 3
3 2 4 1

-1

解释: 任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。

示例 3：

5 3
3 5 1 2 6

25

解释:

从 [3, 5, 1, 2, 6] 开始。

合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。

合并 [3, 8, 6]，成本为 17，剩下 [17]。

总成本 25，这是可能的最小值。

提示：

• $n == stones.length$
• $1 <= n <= 30$
• $1 <= stones[i] <= 100$
• $2 <= k <= 30$

SOURCE

合并石头的最低成本