提高-⏱ 1000ms💾 256MB#P7099🏷️ 动态规划单调队列

题目描述

走廊上有 $n$ 盏灯,点亮第 $i$ 盏灯的代价为 $a_i$。 要求任意连续 $m$ 盏灯中至少有一盏被点亮,求点亮总代价的最小值。

输入格式

第一行两个正整数 $n$ 和 $m$; 第二行 $n$ 个正整数 $a_i$。

输出格式

一行一个整数:最小总代价。

数据范围

$$1 \le m \le n \le 2 \times 10^5$$
,
$$1 \le a_i \le 10^9$$
。

样例输入 #1
5 3
1 2 5 6 2
样例输出 #1
4
样例输入 #2
2 1
5 3
样例输出 #2
8