No submission language available for this problem.

【题目背景】

公主被恶龙抓走了，唯一能够救出公主的勇者准备出发营救公主。 在这位勇者出发前，国王请你帮助勇者规划营救路线，好尽早营救出公主。

【题目描述】

从勇者所在的1号村庄到恶龙所在的山洞中一共会经过 $n$ 个村庄，村庄 $i$ 和 $i+1$ 有一条双向的路连接，走这条路要耗费时间 $a_i$ 。

从未有人踏足过恶龙所在的山洞，所以第 $n$ 个村庄和山洞之间不存在公路，就算是足智多谋的你也无能为力，只能靠勇者的智慧和勇气进入。 所以你需要做的就是帮助勇者规划从1号村庄到 $n$ 号村庄的行进方案，终点必须是 $n$ 号村庄，否则勇者无法进入山洞营救公主。

国王拿出珍藏多年的传送石帮助勇者，但是传送石是消耗品，只能使用一次。 传送石的传送半径为 $k$ ，如果勇者当前在 $i$ 村庄，他可以使用传送石立刻到达 $i-k$ 村庄和$i+k$ 村庄。如果目标村庄编号小于1则为1 ，大于 $n$ 则为 $n$ 。

为了尽快营救出公主，请你规划出从1号村庄到 $n$ 号村庄消耗时间最短的方案。

注意：勇者不必经过全部村庄，使用传送石不消耗时间

【输入格式】

第一行包含两个整数 $n,k$ 。 第二行包含 $n-1$ 个整数，第 $i$ 个整数表示 $i$ 号村庄和 $i+1$ 号村庄间走路需要的耗时 $a_i$ 。

【输出格式】

一行整数，表示最短消耗时长。

【样例】

输入数据1

4 0
1 2 3

输出数据1

6

输入数据2

4 1
1 2 3

输出数据2

3

【说明】

样例2说明

在 3 处使用，传送到 4，答案为 3，可以证明这个是最小值。

1 $\leq$ $a_i$ $\leq$ $10^{12}$

0 $\leq$ $k$ $\leq$ $10^{6}$

1 $\leq$ $n$ $\leq$ $10^{6}$