E2-股票IV

题面

假设您有一个数组，第i个元素是第i天给定股票的价格。

设计算法以找到最大的利润。您最多可以完成k次交易。

请注意，无法同时进行多项交易（即必须先出售股票才能再次购买）

输入

多组输入数据

每组数据第一行两个数n,k，表示总天数和最多交易次数。($1\le n,k \le 10^3$)

接下来一行n个数表示股票的价格($1\le a_i \le 10^9$)

输出

每组数据一行一个数

输入样例

5 2
1 2 3 4 5

输出样例

4