Background
Special for beginners, ^_^
Description
李大志做了一个白日梦。
一共有n个城市,编号为1,2,3,…n。城市 i和城市i+1有一条双向高速公路连接,走这条路要耗费时间a i。
他现在要去旅游,起点 1号城市,终点是n城市,i号城市只能到达 i+1和i−1号城市。
不仅如此,他还有一个传送器,传送距离为k,也就是可以从i城市传送到i−k或i+k号城市。如果传送的城市编号小于1则为1,大于n则为n。
但是他的传送器电量不足,只能传送一次,同时由于他出门的时候忘记关门了,他想尽快的结束,于是就想问你结束最快的时间是多少。
注意:他不必访问所有的城市,使用传送器不耗费时间
Format
Input
两行,第一行两个正整数
n,k(1≤n≤1000000,0≤k<n)。
第二行n−1个整数,第i个表示
(a i≤10000000)。
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.
能给我一下思路吗?(c++)