秘宝猎人

题目描述

在传说中的“万象之森”中，隐藏着许多失落的古代战备计划。作为一名秘宝猎人，你发现这些计划在黑市上的价格每天都在变化。

已知未来 $n$ 天内，每天该战备计划的价格为 $a_i$。你手中最多只能同时持有一份计划。你可以随时买入或卖出。

由于黑市的准入证有限，你在这 $n$ 天内累计最多只能进行 $k$ 次交易（一次买入加一次卖出算作一次完整的交易）。你必须在开启下一次交易前卖掉当前手里的这份计划。

请问到第 $n$ 天结束时，你最多能赚取多少利润？

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示总天数和最大允许交易次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每天该战备计划的价格。

输出格式

输出一个整数，表示能获得的最大利润。

输入输出样例 #1

输入 #1

3 2
2 4 1

输出 #1

2

输入输出样例 #2

输入 #2

6 2
3 2 6 5 0 3

输出 #2

7

数据范围

对于 $60\%$ 的数据，$1 \le n \le 1000$，$1 \le k \le 100$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le k \le 100$，$0 \le a_i \le 10^9$。 注意：由于 $k$ 的限制较小，建议使用状态机动态规划求解。