题目描述

给定一个长度为$N$的数组，数组中的第$i$个数字表示一个给定股票在第$i$天的价格。

设计一个算法来计算你所能获取的最大利润，你最多可以完成$k$笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。

样例输入

第一行包含整数$N$和$k$，表示数组的长度以及你可以完成的最大交易笔数。

第二行包含$N$个非负整数，表示完整的数组。

样例输出

输出一个答案表示最大的收益。

样例

样例一

3 2
2 4 1

2

样例解释：

在第1天的时候买入，在第2天的时候卖出。

数据范围

$1 \le N \le 10^{5}$

$1 \le k \le 100$

每一个交易的价格为不大于$10000$的非负整数。