P4803.第2题-老张爬山
题目内容
老张爱好爬山。不过老张认为太过频繁的爬山对膝盖不太好。
老张给自己定了一个规则，原则上只能每隔一天爬山一次，如果今天爬山了，那么明天就休息一天不爬山了。但老张认为凡事都有例外，所以他给了自己 k 次机会，在昨天已经爬山的情况下，今天仍然连续爬山！
换句话说就是老张每天最多爬山一次，原则上如果昨天爬山了那么今天就不爬山，但最多有 k 次打破原则的机会。
爬山让人心情愉悦，所以老张每天爬山都能获得一定的愉悦值，请帮老张规划一下爬山计划来获得最大的愉悦值之和。
输入描述
第一行两个整数 n 和 k ，表示老张正在计划未来 n 天的爬山计划以及 k 次打破原则的机会。
第二行 n 个整数 a1,a2,...,an ，其中 ai 表示接下来第 i 天如果进行爬山可以获得的愉悦值。
1≤n≤2000，1≤k≤1000，1≤ai≤10000
输出描述
输出一行一个数，表示老张能在最佳爬山计划下获得的愉悦值之和。
样例1
输入
7 1
1 2 3 4 5 6 7
输出
19
说明
最优的方案是选择第 2、4、6 天爬山，并在第 7 天打破一次原则（因为第 6 天已经爬过了，原则上不能继续爬山，需要使用一次打破原则的机会）。
