题目内容

小李是一名自由职业者，在未来 $N$ 天里，每天都有一个可选的任务订单。如果他选择在第 $i$ 天工作，就可以获得 $A_i$ 的收入。然而，连续工作会让小李过度劳累，因此他给自己定下规则：如果某一天工作了，则第二天必须休息，不能工作。

不过，小李拥有 $K$ 次“豁免权”，每使用一次豁免权，就可以打破一次上述规则，即在前一天已经工作的情况下，次日仍然可以继续工作。

每天小李至多完成一个订单。请你帮他规划这 $N$ 天的工作安排，使得获得的总收入最大化。

约束：$1 \le N \le 2000$，$1 \le K \le 1000$，$1 \le A_i \le 10000$，所有输入均为整数。

输入描述

第一行包含两个整数 $N$ 和 $K$，分别表示计划的天数和豁免权的次数。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，其中 $A_i$ 表示第 $i$ 天工作可以获得的收入。

输出描述

输出一个整数，表示在最优安排下可以获得的最大总收入。

样例1

输入

3 0
2 1 3

输出

5

说明

没有豁免权（$K=0$）时，不能连续两天工作。 如果选择第 1 天和第 3 天工作，收入为 $2+3=5$；若第 1 天和第 2 天工作，违反规则不允许；单独工作最大为 3。因此最大总收入为 5。

样例2

输入

4 1
10 20 30 40

输出

80

说明

有 1 次豁免权，可以允许多连续工作一天。 一种最优方式是：第 1 天工作（收入 10），第 2 天休息，第 3 天工作（收入 30），第 4 天使用豁免继续工作（收入 40），总收入 $10+30+40=80$。 若尝试连续工作更多天（如第 2、3、4 天），仅 1 次豁免无法支撑，收入较低。

样例3

输入

5 2
5 1 1 1 5

输出

12

说明

有 2 次豁免权。可行方案：第 1 天工作（收入 5），第 2 天使用豁免继续工作（收入 1），第 3 天休息，第 4 天工作（收入 1），第 5 天使用豁免继续工作（收入 5）。总收入 $5+1+1+5=12$。 其他方案如连续工作三天以上需要更多豁免权，不可行。

样例4

输入

1 0
100

输出

100

说明

只有 1 天，无需豁免权，直接工作即可获得收入 100。