You are given an array price where prices[i] denotes the price of a stock on the ith day. You want to maximize the profit by buying a stock and then selling it at a higher price.

Suppose you can do at most k transactions (k buys and k sells), what is the maximum profit that you can make?

Note:

• Return 0 if you cannot make a profit.
• You cannot buy/hold more than 1 stock at a time.
• You need to sell a stock before buying again.
• You can sell a stock and buy it again on the same day.

Examples

prices: [6, 1, 4, 2, 5, 3]
k: 2
Answer: 6

Explanation
Buy on day 2 (price: 1) and Sell on day 3 (price: 4).
Buy on day 4 (price: 2) and Sell on day 5 (price: 5).
Profit: (4 - 1) + (5 - 2) = 6.

prices: [6, 1, 4, 2, 5, 3]
k: 1
Answer: 4

Explanation
Buy on day 2 (price: 1) and Sell on day 5 (price: 5).
Profit: (5 - 1) = 4.

prices: [1, 2, 3, 4, 5]
k: 4
Answer: 4

Explanation
Buy on day 1 (price: 1) and Sell on day 5 (price: 5).
Profit: (5 - 1) = 4.

prices: [1, 2, 3, 4, 5]
k: 0
Answer: 0

Explanation
Since k is 0, no transactions can be done.

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input has two lines:

• Two integers ‘n’ denoting the size of the array and k.
• n space-separated integers denoting the array.

Output Format

For each test case, the output contains a line with one integer denoting the max profit.

Sample Input

4
6 2
6 1 4 2 5 3
6 1
6 1 4 2 5 3
5 4
1 2 3 4 5
5 0
1 2 3 4 5

Expected Output

6
4
4
0

Constraints

1 <= T <= 100
0 <= k <= 100
1 <= n <= 1000
1 <= pricesi <= 1000