最短旅行时间

题目描述

有 $n$ 个城市，编号为 $1,2,\dots,n$。城市 $i$ 与城市 $i+1$ 之间有一条双向公路，走这条路需要时间 $a_i$。

你从 $1$ 号城市出发前往 $n$ 号城市。除公路外，你还有一个传送器，传送距离为 $k$：使用后可以从城市 $i$ 直接到达城市 $i-k$ 或城市 $i+k$；若目标编号小于 $1$ 则视为 $1$，大于 $n$ 则视为 $n$。传送器只能使用一次，且使用它不消耗时间。

你不需要访问所有城市。求从 $1$ 号城市到 $n$ 号城市所需的最短时间。

输入格式

两行。第一行两个正整数 $n,k$（$1\le n\le 10^6$，$0\le k<n$）。

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

输出格式

输出一个整数，表示最短时间。

样例输入 1

4 0
1 2 3

样例输出 1

6

样例输入 2

4 1
1 2 3

样例输出 2

3