100 #P1173. E43*【单调队列】连续m个至少选一个的最小总和[烽火传递]

E43*【单调队列】连续m个至少选一个的最小总和[烽火传递]

NOIP 2010 提高组初赛 · 完善程序

【题意】

nn 个数的序列 aia_i 中选若干个数,使得所选数的和最小。

要求在连续 mm 个数里至少选一个。

【输入格式】

第一行两个整数 n mn \ mmn2×105m \le n \le 2 \times 10^5)。

下来 nn 个数 aia_i0ai10000 \le a_i \le 1000)。

【输出格式】

一个整数,表示最小总和。

【样例输入】

5 3
1 2 5 6 2

【样例输出】

4