318002 - 烽火传递

18.2 烽火传递(Beacon) Tyvj 1313

烽火台又称烽燧,是重要的军事防御设施,一般建在险要或交通要道上。一旦有敌情发生,点燃柴草,以浓烟和火光传递军情。

某两座城市之间有 n 个烽火台,每个烽火台发出信号都有一定代价。为了使情报准确地传递,在连续 m 个烽火台中至少要有一个发出信号。请计算总共最少花费多少代价,才能使敌军来袭之时,情报能在这两座城市之间准确传递。

输入

第一行为两个整数 nm,其中 n 表示烽火台的个数, m 表示在连续 m 个烽火台中至少要有一个发出信号。接下来 n 行,每行一个数 w_i,表示第 i 个烽火台发出信号所需代价。

输出

仅一行,表示答案。

样例

输入

5 3 
1 
2 
5 
6 
2

输出

4

提示

对于 50\% 的数据,m\le n\le1 000

对于 100\% 的数据,m\le n\le100 000w_i\le100

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题