从城池i到城池i+1有一条驿道相连，快马传递需耗时ai。将军欲巡视疆土，每次必从都城（城池 1）出发，至边关（城池 n）终止。  

军中有一件急行令符，可令兵马瞬息传送至前方或后方k座城池（若越界则至边界）。  但是此令符仅能使用一次，且将军希望尽快完成巡视（即尽快到达城池n），问最短需多少时日？

【样例输入 2】

5 1  

1 2 3 4  

【样例输出2】  

6  

【样例说明】  

样例 1：令符无效，全程走驿道，总耗时10；  

样例 2：在城池4使用令符，传至城池5，总耗时1+2+3+4=6。

【数据范围】

40%数据，10<=n,k<=10000，0<ai<100000。

100%数据，10<=n,k<=1000000，0<ai<100000。