若干年后，由于种种原因宇宙中只存在n个星系,并且KK统治了这些星系。
为了查看星系的状况，KK定期对这些星系进行走访。每次走访时，他会从1号星系到n号星系并在经过的星系进行访问，KK从星系i到星系i+1的时间与从星系i+1到星系i的时间都为ai,其中终点必须为星系n。
KK在访问的时候可以借助黑洞进行星际跳跃，跳跃的半径为k,即可以跳跃到编号为i-k和编号为i+k的星系,跳跃的时间为0。
如果目标星系的编号小于1则为1，大于n则为n,但是只能跳跃一次。
求解KK的最少访问时间，KK不必访问所有星系。
输入
输入共两行。
第一行为两个整数n和k。
第二行为n-1个整数，表示ai。
输出
输出共一行，为最少时间。
样例
| 标准输入 复制文本 |
4 0 1 2 3 |
| 标准输出 复制文本 |
6 |
| 标准输入 复制文本 |
4 1 1 2 3 |
| 标准输出 复制文本 |
3 |
提示
数据范围:
0<=n<=1000000
0<=k<=1000000
0<ai<=1e9
样例解释:
样例一:
因为跳跃距离为0，所以只能一个星系一个星系访问，最少时间为6。
样例二:
因为跳跃距离为1，所以KK可以在星系3进行跳跃到星系4，最少时间为3。