题目描述

有一个长度为 $n$ 的数列 $(a_1, a_2, \cdots, a_n)$，初始时只有 $a_1$ 和 $a_n$ 是黑色的，其它数都是白色的。小蓝可以选择若干白色的数将其染黑，但是必须满足相邻的两个黑色的数之间最多包含 $k$ 个白色的数，他想让所有黑色的数的和尽可能小，请问他最少可以让所有黑色的数的和为多少。

输入格式

输入的第一行包含两个整数 $n, k$，用一个空格分隔。

第二行包含 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

8 2
5 2 7 5 5 9 3 7

19

解释 #1

选择染黑 $a_2, a_5$，黑色的数的和为 $5 + 2 + 5 + 7 = 19$。

数据范围

• 对于 $20\%$ 的评测用例，$1 \leq n \leq 10$；
• 对于 $50\%$ 的评测用例，$1 \leq n \leq 5000$；
• 对于所有评测用例，$0 \leq k < n \leq 10^5$，$1 \leq a_i \leq 10^6$。