Description
李大志做了一个白日梦。
一共有
�
n个城市，编号为
1
,
2
,
3
,
…
�
1,2,3,…n。城市
�
i和城市
�
+
1
i+1有一条双向高速公路连接，走这条路要耗费时间
�
�
a
i
。
他现在要去旅游，起点是
1
1号城市，终点是
�
n城市，
�
i号城市只能到达
�
+
1
i+1和
�
−
1
i−1号城市。
不仅如此，他还有一个传送器，传送距离为
�
k，也就是可以从
�
i城市传送到
�
−
�
i−k或
�
+
�
i+k号城市。如果传送的城市编号小于
1
1则为
1
1，大于
�
n则为
�
n。
但是他的传送器电量不足，只能传送一次，同时由于他出门的时候忘记关门了，他想尽快的结束，于是就想问你结束最快的时间是多少。
注意：他不必访问所有的城市，使用传送器不耗费时间
Format
Input
两行，第一行两个正整数
�
,
�
(
1
≤
�
≤
1
0
6
,
0
≤
�
<
�
)
n,k(1≤n≤10
6
,0≤k<n)。
第二行
�
−
1
n−1个整数，第
�
i个表示
�
�
(
�
�
≤
1
0
8
)
a
i
(a
i
≤10
8
)。
Output
一个整数，表示答案。
Samples
输入数据 1
4 0
1 2 3
输出数据 1
6
输入数据 2
4 1
1 2 3
输出数据 2
3
Limitation
1s, 1024KiB for each test case.
