题目描述

李大志做了一个白日梦。

一共有$\,n\,$个城市，编号为$\,1,2,3,\dots n\,$。城市$\,i\,$和城市$\,i+1\,$有一条双向高速公路连接，走这条路要耗费时间$\,a_i$。

他现在要去旅游，起点是$\,1\,$号城市，终点是$\,n\,$城市，$i\,$号城市只能到达$\,i+1\,$和$\,i-1\,$号城市。

不仅如此，他还有一个传送器，传送距离为$\,k$，也就是可以从$\,i\,$城市传送到$\,i-k\,$或$\,i+k\,$号城市。如果传送的城市编号小于$\,1\,$则为$\,1$，大于$\,n\,$则为$\,n$。

但是他的传送器电量不足，只能传送一次，同时由于他出门的时候忘记关门了，他想尽快的结束，于是就想问你结束最快的时间是多少。

注意：他不必访问所有的城市，使用传送器不耗费时间

输入格式

两行，第一行两个正整数$\,n,k\,(1\le n \le 10^6,\,0\le k \lt n)$。

第二行$\,n-1\,$个整数，第$\,i\,$个表示$\,a_i\,(a_i\le 10^8)$。

输出格式

一个整数，表示答案。

输入输出样例

4 0
1 2 3

6

4 1
1 2 3

3