炼金工坊

题目描述

在一座名为“阿卡姆”的炼金工坊里，炼金大师梅林每天都会调制出一种神奇的“长生不老泉”初号液。由于初号液性质极不稳定，它在市场上的价格每天都在波动。

已知未来 $n$ 天内，每天初号液的价格为 $a_i$。作为梅林的助手，你负责在市场上买卖这些液体。你手中最多只能持有一份液体。你可以在任何一天买入一份液体，也可以在任何一天卖出。

由于炼金工坊的规定非常严格，你面临两个限制：

1. 交易次数限制：由于市场配额有限，这 $n$ 天内你累计最多只能进行 $k$ 次交易（买入一次并卖出一次算一次完整交易）。
2. 冷冻期限制：每次卖出液体后，为了消除残留的炼金气息，你必须休息一天（即冷冻期）才能进行下一次买入。例如，你在第 $i$ 天卖出，最早只能在第 $i+2$ 天再次买入。

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

输入格式

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

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每天初号液的价格。

输出格式

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

输入输出样例 #1

输入 #1

5 2
1 2 3 0 2

输出 #1

3

输入输出样例 #2

输入 #2

6 1
1 3 2 8 4 9

输出 #2

7

数据范围

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

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le k \le 100$，$0 \le a_i \le 10^9$。