题目背景

本题数据范围扩大至$10^7$,请同学们注意卡常

$by$ $\color{orange}XuanXuan16888$

题目描述

小A入职网络某游戏公司后，写了他的第一个Android小游戏。

有$n$个方格一字排开，编号依次为$1$到$n$，游戏者初始在$1$号方格，最后要冲到$n$号方格。

可是游戏者每次往前冲的最长距离为$k$，也就是说如果游戏者当前在i号方格，那么他下一步只能冲到[$i+1$,$i+k$]号范围内的方格。可是经过第i号方格会掉$a[i]$滴血（如果$a[i]$为负数，那么就相当于补充−$a[i]$滴血啦！）

小A想知道，对于给定的$n,k$以及游戏方格，游戏者在从1号方格冲到$n$号方格（初始在$1$号方格，最终必须停在$n$号方格）过程中一共最少可以掉多少滴血？（显然答案也有可能是负数）

输入格式

第一行两个正整数$n$和$k$，意义见题面描述。

第二行$n$个整数，第$i$个数字为$a[i]$。

输出格式

一行一个整数，表示最少掉多少滴血。注意初始在$1$号位置就要掉$a[1]$的血。

样例 #1

样例输入 #1

3 3
-4 -3 -2

样例输出 #1

-9

样例 #2

样例输入 #2

20 7
-834 140 807 521 -926 -150 -699 -554 241 429 307 -609 -895 419 23 306 18 168 595 647

样例输出 #2

-4020

样例 #3

样例输入 #3

10 3
95 482 772 373 133 318 337 455 760 47

样例输出 #3

852

提示

请注意常数因子给程序带来的影响。

计分规则为取最小值，如果你没有在全部测试点中均正确，那么你将获得 $0\text{pts}$ 的好成绩。