题目描述

小 K 打下的江山中共有 $n$ 个城市，编号为 $1$ 到 $n$。

城市 $i$ 和城市 $i+1$ 之间有一条双向高速公路，经过这条高速公路需要花费 $a_i$ 的时间。

小 K 为了关心人民生活，会从 $1$ 号城市出发前往 $n$ 号城市，并访问途中经过的城市。最终必须到达 $n$ 号城市，但不要求访问所有城市。

小 K 还有一个传送器，传送半径为 $k$。

当小 K 位于城市 $i$ 时，可以使用传送器传送到：

• 城市 $i-k$；
• 城市 $i+k$。

如果目标城市编号小于 $1$，则实际传送到城市 $1$；如果目标城市编号大于 $n$，则实际传送到城市 $n$。

传送器最多只能使用一次，并且使用传送器不需要花费时间。小 K 也可以选择不使用传送器。

请计算小 K 从城市 $1$ 到达城市 $n$ 所需要的最短时间。

输入格式

第一行输入两个整数 $n$、$k$，分别表示城市数量和传送器的传送半径。

第二行输入 $n-1$ 个正整数 $a_1,a_2,\ldots,a_{n-1}$，其中 $a_i$ 表示经过城市 $i$ 与城市 $i+1$ 之间高速公路所需的时间。

输出格式

输出一个整数，表示小 K 从城市 $1$ 到达城市 $n$ 所需的最短时间。

样例

4 0
1 2 3

6

4 1
1 2 3

3

样例解释

样例 $1$ 中，传送半径为 $0$，使用传送器无法改变所在城市，因此直接沿高速公路从城市 $1$ 前往城市 $4$。

所需时间为：

因此答案为 $6$。

样例 $2$ 中，可以先从城市 $1$ 前往城市 $3$，花费时间：

然后在城市 $3$ 使用传送器，直接传送到城市 $4$，传送不消耗时间。

因此最短时间为 $3$。

数据范围

所有测试数据满足：

$n \ge 2$。

$a_i>0$。

各测试点的数据范围如下：

• 测试点 $1\sim 10$：$n\le 100$，$k\le 100$，$a_i\le 10^5$；
• 测试点 $11\sim 20$：$n\le 3\times 10^3$，$k\le 3\times 10^3$，$a_i\le 10^9$；
• 测试点 $21$：$n\le 10^5$，$k\le 10^5$，$a_i\le 10^{12}$；
• 测试点 $22$：$n\le 2\times 10^5$，$k\le 2\times 10^5$，$a_i\le 10^{12}$；
• 测试点 $23$：$n\le 5\times 10^5$，$k\le 5\times 10^5$，$a_i\le 10^{12}$；
• 测试点 $24\sim 25$：$n\le 10^6$，$k\le 10^6$，$a_i\le 10^{12}$。

注：原题“数据范围”中写有 $k\ge 1$，但样例 $1$ 中 $k=0$，两者存在不一致。