当前没有测试数据。

题目描述

小 $H$ 晚上会兼职在市场上摆摊销售商品。他要在 $n$ 天内选择某几天营业，以最大化他的利润。然而，他有一些特殊的规定和限制。

每天能获得的收益是可以预知的，即如果他选择在第 $i$ 天选择摆摊，就可以获得 $p_i$ 元的收益。

但是每天卖东西非常的消耗精力，他的疲劳度会限制摆摊的天数，每摆摊一天，疲劳度就会加 $1$。要求无论何时，小 $H$ 的疲劳度不能超过 $F$。

如果他选择这天休息，那么疲劳度就会减少 $1$，要求如果选择休息就必须一直休息到疲劳度恢复为 $0$ 为止，才能重新摆摊。当疲劳度为 $0$ 时，即使继续休息，疲劳度仍然保持 $0$。第一次开始摆摊时，小 $H$ 的疲劳度为 $0$。

为了保证不影响学习，$n$ 天结束时，他的疲劳度必须恢复为 $0$。

请帮小 $H$ 计算一下在这样的条件下最大收益是多少。

输入格式

第一行两个正整数 $n, F$。

接下来 $n$ 行，每行一个正整数 $p_i$。

输出格式

输出一个整数，表示在满足所有限制条件的情况下，小 $H$ 能获得的最大收益。

样例

输入

5 2
5
3
4
2
10

输出

9

输入

10 3
8
7
6
1
5
9
2
4
6
10

输出

35

数据范围

对于 $20\%$ 的数据，满足 $1 \le n \le 10$，$1 \le F \le 2$。

对于 $100\%$ 的数据，满足 $1 \le n \le 10^4$，$1 \le p_i \le 1000$，$1 \le F \le 500$。