题目描述

小明计划在接下来的 $n$ 天中选择一些天摆摊。第 $i$ 天摆摊可以获得 $p_i$ 元收益，并使疲劳值增加 $1$。疲劳值不能超过 $F$，开始时疲劳值为 $0$。

某一天不摆摊时，疲劳值减少 $1$，但不会小于 $0$。一旦在疲劳值大于 $0$ 时开始休息，就必须连续休息到疲劳值恢复为 $0$，之后才能再次摆摊。疲劳值为 $0$ 时可以继续休息。

第 $n$ 天结束时，疲劳值必须为 $0$。请计算能够获得的最大总收益。

输入格式

第一行包含两个整数 $n,F$，分别表示天数和疲劳值上限。

接下来 $n$ 行，第 $i$ 行包含一个整数 $p_i$，表示第 $i$ 天摆摊的收益。

输出格式

输出一个整数，表示最大总收益。

5 2
5
3
4
2
10

9

数据范围与提示

• $1 \le n \le 10000$
• $1 \le F \le 500$
• $1 \le p_i \le 1000$