题目描述

某机器在接下来的 $n$ 天时间里，有不同的产出。在第 $i$ 天，它的产出为 $a_i$。这台机器最多只能连续工作 $m$ 天，若连续工作 $m$ 天，则至少要休息一天。请问应该让机器在哪些天工作，所得产出之和达到最大？

输入格式

• 第一行：两个整数表示 $n$ 与 $m$
• 第二行：$n$ 个整数表示 $a_1,a_2,\dots,a_n$

输出格式

• 单个整数表示答案

5 2
1 2 3 4 5

12

数据范围

• $30\%$ 的数据，$1\leq n\leq 20$
• $60\%$ 的数据，$1\leq n\leq 5000$
• $100\%$ 的数据，$1\leq m\leq n\leq 200,000$
• $1\leq a_i\leq 1,000,000,000$