← 返回题目列表

Codeforces · 940/E

E. 现金返还

中文机器翻译题面 查看原题

由于您是最好的幽灵王,位于文尼察中心的 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。