由于您是最好的幽灵王,位于文尼察中心的 Nizhniy Magazin «Mir» 为您提供折扣。
给定一个长度为 n 的数组 a 和一个整数 c。
长度为 k 的某个数组 b 的值是其元素之和,除了 $$\left\lfloor \frac{k}{c} \right\rfloor$$ 之外的最小元素。例如,c = 2 的数组 [3, 1, 6, 5, 2] 的值为 3 + 6 + 5 = 14。
在将 a 划分为连续子数组的所有可能的分区中,输出这些子数组的值的最小可能总和。
输入
第一行包含整数 n 和 c (1 ≤ n, c ≤ 100 000)。
第二行包含 n 个整数 ai (1 ≤ ai ≤ 109) — a 的元素。
输出
输出一个整数 - a 的某个分区的这些子数组的值的最小可能总和。
示例
输入 #1
3 5 1 2 3
输出 #1
6
输入 #2
12 10 1 1 10 10 10 10 10 10 9 10 10 10
输出 #2
92
输入 #3
7 2 2 3 6 4 5 7 1
输出 #3
17
输入#4
8 4 1 3 4 5 5 3 4 1
输出#4
23
注意
在第一个示例中,任何分区的总和都是 6。
在第二个示例中,最佳分区之一是 [1, 1]、[10, 10, 10, 10, 10, 10, 9, 10, 10, 10],其值分别为 2 和 90。
在第三个示例中,最佳分区之一是 [2, 3]、[6, 4, 5, 7]、[1],其值分别为 3、13 和 1。
在第四个示例中,最佳分区之一是 [1]、[3, 4, 5, 5, 3, 4]、[1],其值分别为 1、21 和 1。