STK - Stock

Alex heard a lot about investing in the stock market and now wants to do it to earn some profit. Being a new investor he is scared of the risks in the stock market, so he decides that at any instance he will not have more than one stock with him. It is also decided that on a particular day he can either buy or sell at most one stock (only one transaction allowed). Now given the prices of one particular stock over the period of n days Alex decides he will make at most k buys and k sells.

Write a code to help Alex to maximize his profit.

Input

First line contains an integer T (<=100), number of test cases.

Each test case will have n (<=3000) and k (1<=k<=n/2), is the number of days and the maximum buys/sells allowed respectively.

(Value of the prices are in range of unsigned 32-bit integer.)

Next line will have n space separated integers denoting the price of stock over n days.

Output

For each test case output one line stating the maximum profit.

Example

Input:
3
10 3
2 7 3 9 8 7 9 7 1 9
10 1
2 7 3 9 8 7 9 7 1 3
10 2
2 7 3 9 8 7 9 7 1 9

Output:
19
7
15

Explanation

1st test case, Alex would buy on 1st day and sell it on the 2nd day, and then buy another on the 3rd day and sell it on the 4th, finally buys on 9th day and sells on the 10th day. So profit = (7-2)+(9-3)+(9-1) = 19.

2nd test case Alex would buy on 1st day and sell it on the 4th(or 7th) day. So profit = 9-2 = 7.

2nd test case Alex would buy on 1st day and sell it on the 4th day, and then buy another on the 9th day and sell it on the 10th day. So profit = (9-2)+(9-1) = 15.


Added by:Abhra
Date:2014-04-05
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2021-05-11 21:56:43 Simes
@Tensor - that's still true. My incorrect solution gives the same answers as yours but also got AC.
2015-03-12 20:35:30 Tensor
I wrote the code not considering (K) and get accepted ?!!!!!, test cases are wrong it gives me 21, 15, 21 and my code get accepted, please fix the test data or the problem at all!!!
2014-05-27 21:34:57 Andy
you don't need DP to solve this problem

Last edit: 2014-05-27 21:45:39
2014-04-05 12:18:14 Francky
Please let the constraints on the price : what is the max price possible ?

Reply: Question modified. The prices are in range of 32 bit integers.

--ans(Francky)--> Thanks, but be more precise please : signed or unsigned 32bit integers ?

-- yes

Last edit: 2014-04-05 12:17:52
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.