哈利需要穿过一个一维魔法阵，这个魔法阵有编号依次为1,2,3....n的n个节点。哈利在魔法阵的节点上可以发动传送魔法，这个魔法将哈利向前或向后传送k个节点，并且不消耗时间，但只能使用一次。魔法阵不会允许他传送出去：当传送到编号小于1的节点时将停留在1号节点，当传送到编号大于n的节点时将停留在n号节点。现在，哈利在1号节点，他非常着急到达n号节点拿到他的魔法帽，最少需要多长时间？

第一行，有单个空格分隔的两个整数n,k，n表示节点个数,k表示在魔法阵的节点上发动传送魔法时向前或向后传送的节点个数。

接下来n-1行，每行一个整数a_i，依次表示哈利从i号节点与i+1号节点所需的时间。

对于20%的数据：

1\le n \le 10^2；

0\le k \le 10^2；

1\le a_i \le 10^5。

对于40%的数据：

1\le n \le 10^3；

0\le k \le 10^3；

1\le a_i \le 10^9。

对于60%的数据：

1\le n \le 10^5；

0\le k \le 10^5；

1\le a_i \le 10^{12}。

对于100%的数据：

1\le n \le 10^6；

0\le k \le 10^6；

1\le a_i \le 10^{12}。

一个整数，所需要的时间。

样例1：

在1号节点发动魔法，剩余的2、1走过去。

样例2：

既然传送没有什么用，那就全走过去。