走访城市

时间限制:1s

空间限制:64MB

题目背景

现有编号\(1\)~\(n\)的\(n\)个城市，编号相邻的城市之间有一条交通道路相连。现在你要从编号\(1\)的城市走到编号\(n\)的城市，走每条交通道路需要的用时不等，为\(t_i\)。

除了使用交通道路外，你还可以使用一次传送器，使用传送器不消耗时间。传送器的半径为\(k\)，即你可以从\(x\)号城市传送到\(x+k\)号城市，如果编号\(x+k\)存在。

问：从\(1\)号城市到\(n\)号城市，至少需要多长时间？

输入格式

第一行两个整数\(n,k\)，表示城市数量和传送器半径

第2行\(n-1\)个整数，按顺序表示连接\(i\to i+1\)的交通道路的用时。

输出格式

一个整数，表示最少时间数

样例输入1

4 0
1 2 3

样例输出1

6

样例1解释

\(k=0\)，传送器没有作用

所以走三条交通道路，用时为\(6\)

样例输入2

4 1
1 2 3

样例输出2

3

样例2解释

使用传送器从城市\(3\)到城市\(4\)

数据范围及限制

对于前\(40\%\)的数据，\(k=0,1 < n\le 10\)

对于前\(80\%\)的数据，\(0\le k<n\le 10^2\)

对于\(100\%\)的数据，\(0\le k< n\le 10^5, 1 \le a_{i}\le 10^4\)