Problem1419--PIPI炒股Ⅱ

1419: PIPI炒股Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 448  Solved: 158
[Submit] [Status] [Web Board] [Creator:]

Description

考虑股票市场,一共有n天。对于第i天,pipi知道股票的价格是a[i]元。
完成一笔交易是指,在第i天以a[i]元买入一支股票,然后在第j天(j>i)以a[j]元卖出这支股票。
PIPI最多可以进行k次交易。注意不能同时执行多笔交易,即完成一次买卖后,才能进行下一次买卖,不能手上同时持有多支股票。
同时,PIPI在每一天只能在合法的条件下选择卖、买、啥也不干其中之一。
请你算出n天后PIPI最多能赚多少钱。

Input

第一行输入两个整数n,k,分别表示天数和最多能够进行的交易次数。(n<=5000,k<=1e9)
接下来n个整数,表示每天股票的价格a[i]。(a[i]<=30000)

Output

输出n天后PIPI最多能赚多少钱。

Sample Input

6 2
3 2 6 5 0 3

Sample Output

7

Source/Category

中等