题目描述

山谷里沿一条直线排着 $n$ 座信号塔，从前往后编号 $1\sim n$。第 $i$ 座塔转发一次信号需要开销 $a_i$。

现在要从 $1$ 号塔把信号送到 $n$ 号塔。信号只能由已经收到信号的塔往下游转发，而且单次转发的距离有限：相邻两次被使用的塔，编号之差不能超过 $k$（也就是说中间最多跳过 $k-1$ 座塔）。

凡是参与转发的塔都要付一次开销，$1$ 号塔和 $n$ 号塔必须参与。求完成这次接力所需的最小总开销。

输入格式

第一行两个整数 $n,k$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

一行一个整数，表示最小总开销。

输入输出样例 #1

输入 #1

5 2
1 3 2 5 4

输出 #1

7

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le k\le n$，$0\le a_i\le 10^9$。不超过 $k=2$。