光骓者的荣耀

难度：T2

【知识点：前缀与差分】【知识点：条件判断】

前置知识：循环、条件判断、一维数组、累计与区间

题目描述

城市 $1$ 到 $n$ 依次排成一条路线，从城市 $i$ 走到城市 $i+1$ 需要 $a_i$ 时间。你要从城市 $1$ 前往城市 $n$，途中最多使用一次免费传送：在城市 $i$ 使用后，直接到达城市 $\min(i+k,n)$，跳过的路段不耗时。可以不使用传送，不必访问被跳过的城市。求到达城市 $n$ 的最少用时。

输入格式

第一行 $n,k$；第二行 $n-1$ 个正整数，表示各段用时。

输出格式

输出最少用时。

数据范围

本地范围 $2\le n\le1000$，$1\le k\le1000$，$1\le a_i\le10^9$。

样例输入

5 2
3 1 4 2

样例输出

4