分段序列

题目描述

给你一个长度为$n$的数列$a$和整数$c$，你需要把数列$a$分成任意多段。

假设一段长度为$k$，就去掉前$\lfloor \frac{k}{c} \rfloor$小的数，要求最小化剩下的数的和。

输入格式

第一行两个整数，表示$n$，$c$。

第二行$n$个整数，表示序列$a$。

输出格式

一行一个整数，表示答案。

数据范围与提示

对于$100\%$的数据，$1 \leq n$，$c \leq 100000$，$1 \leq a_{i} \leq 10^{9}$。

样例

3 5
1 2 3

6

说明

任何分段的总和都是$6$。

12 10
1 1 10 10 10 10 10 10 9 10 10 10

92

说明

最优解的分段方案之一是$[1,1]$，$[10,10,10,10,10,10,9,10,10,10]$，其值分别为$2$和$90$。

7 2
2 3 6 4 5 7 1

17

8 4
1 3 4 5 5 3 4 1

23