Description

将军平定天下，共收复n座城池，这些城池沿要道依次排列。
从城池i到城池i+1有一条驿道相连，快马传递需耗时ai。将军欲巡视疆土，每次必从都城（城池 1）出发，至边关（城池 n）终止。
军中有一件急行令符，可令兵马瞬息传送至前方或后方k座城池（若越界则至边界）。
但是此令符仅能使用一次，且将军希望尽快完成巡视（即尽快到达城池n），问最短需多少时日？

Input

第一行：城池数n，急行令符传送半径k。
第二行：n-1个整数，依次表示每条驿道所需时间ai。

Output

一个整数，表示最快巡视所需时间。

5 0  
1 2 3 4  

10 

5 1  
1 2 3 4  

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。