给定数组 $$$a_1, a_2, \dots, a_n$$$。您需要将其拆分为 $$$k$$$ 子段(因此每个元素都包含在一个子段中)。
子分段 $$$a_l, a_{l+1}, \dots, a_r$$$ 的权重等于 $$$(r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)$$$。分区的权重是其所有分段的总权重。
找到权重最小的分区。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^4$$$, $$$1 \le k \le \min(100, n)$$$) — 数组 $$$a$$$ 的长度和分区中子段的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^4$$$) — 数组 $$$a$$$。
输出
打印单个整数 — 所有可能分区中的最小权重。
示例
输入 #1
4 2 6 1 7 4
输出 #1
25
输入 #2
4 3 6 1 7 4
输出 #2
21
输入 #3
5 4 5 1 5 1 5
输出 #3
21
注意
第一个示例中的最佳分区如下:$$$6$$$ $$$1$$$ $$$7$$$ $$$\bigg|$$$ $$$4$$$。
第二个示例中的最佳分区如下:$$$6$$$ $$$\bigg|$$$ $$$1$$$ $$$\bigg|$$$ $$$7$$$ $$$4$$$。
第三个示例中的最佳分区之一如下:$$$5$$$ $$$\bigg|$$$ $$$1$$$ $$$5$$$ $$$\bigg|$$$ $$$1$$$ $$$\bigg|$$$ $$$5$$$。