Coding is the closest thing we have to superpower !

1270 : 综合练习-punish
描述

n 个宝箱排成一排,每只宝箱里藏着一只怪物,会对你造成 a_{i} 伤害。现在你需要选择连续的 m 个宝箱,来接受惩罚。因为你使用了某些手段,可以提前知道每个宝箱里怪物造成的伤害。那么问题来了,如何选择可以使得承受的伤害最小。

输入

第一行两个整数 n, m
第二行 n 个整数 a_{i}
数据范围 1 \leq m \leq n \leq 3000,1 \leq a_{i} \leq 100

输出

一行一个整数,表示承受伤害的最小值。

样例

输入

9 4
1 10 10 5 4 8 8 3 7

输出

23
提示

此题由罗靖哲讲解。

语言:
主题: