ADAGROW - Ada and Replant

no tags 

As you might already know, Ada the Ladybug is a farmer. She grows vegetables. At the moment, all her vegetables are in one furrow. She is going to replant them into a few new furrows (while keeping the order of the vegetables).

The total cost of growing the vegetables will be equal to the sum of absolute differences between neighboring vegetables. Ada wants to minimize the cost, can you help her?

Input

The first line of input contain 1 ≤ T ≤ 500 test-cases.

The first line of each test-case contains two integers N, K 1 ≤ N ≤ 2000, 1 ≤ K ≤ 20

The next line contains N integers 0 ≤ Ai < 104, the costs of vegetables.

NOTE: The number of test-cases varies depending on size of array (the longest array won't be a single file more than once).

Output

For each test-cases, print the minimal costs.

Example Input

5
4 2
1 2 5 6
5 1
1 2 5 7 11
6 3
1 3 1 3 1 3
8 2
1 6 2 5 1 6 2 5
5 3
1 9 15 4 11

Example Output

2
10
0
6
5

Additional Information

TEST-CASE-1:
1 2
5 6
TEST-CASE-2:
1 2 5 7 11
TEST-CASE-3:
1 1 1
3 3 3

TEST-CASE-4:
1 2 1 2
6 5 6 5
TEST-CASE-5:
1 4
9 11
15

Example Input 2

1 
7 2 
2 5 7 4 8 8 4 

Example Output 2

5

Example Input 3

1
10 2
4 5 4 3 4 3 2 3 2 3

Example Output 3

4

hide comments
geekypro: 2020-10-16 13:44:23

Can anyone please explain how to approach these kind of problems?

Kaifei Chen: 2020-07-02 03:58:55

Thanks for this nice problem. I really enjoy it.

morass: 2017-10-04 01:15:23

@wcoders: Good day to you - maximum sum of N in single file is 2000 :)

wcoders: 2017-10-03 12:44:31

What is the maximum sum of N from all test cases in a single file ?

morass: 2017-09-10 09:38:41

@Min_25: Thank you! It means very much hearing this from you ^_^

Min_25: 2017-09-09 21:55:15

Nice Problem !

morass: 2017-08-21 12:43:19

@[Rampage] Blue.Mary: Good day to you,

Well I'm not convinced about the part where you choose what to add. If I add EVERYTHING, then I get correct answer (with your program) - anyway it times out -- yet I didn't observe yet, whether/what is wrong :'(

PS: The WA is on TC 7 - soo seems it is "not bad" + your idea is almost similar [considering the kind of algorithm]

Have nice day ^_^

morass: 2017-08-20 22:32:49

@mahilewets: Can't access timus... oh good - seems its solved the ^-^

mahilewets: 2017-08-20 13:35:22

Oh yeah
Now I understand

My solution is incorrect

mahilewets: 2017-08-20 13:33:39

Really, my solution gives "4"

I think it is possible I have not understood the whole difficulty of the problem

I can email ideone.com link with my code to you

Last edit: 2017-08-20 13:33:54

Added by:Morass
Date:2017-08-19
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All