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 containt 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
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 ^_^

[Rampage] Blue.Mary: 2017-08-21 08:11:15

I don't know what's wrong with my program (get WA instead of TLE). Are you sure your test cases are right? If answer is yes, I'll revisit my program's logic.

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
mahilewets: 2017-08-20 13:28:59

Problem reminds of Bicolored Horses from Timus OJ

No, it is not the same problem

Just the statement is similar

morass: 2017-08-20 13:28:05

@mahilewets: Good day to you,

actually you are getting WA on first test-case. (anyway I don't know yet, whether it is mine or your mistake and I can't investigate it before evening). Anyway here is one of the test-case in which our solutions differs:

1
7 2
2 5 7 4 8 8 4

I guess your say "4" .. if it is true can you elaborate? I can't see such solution and atm I have to go so no way to track it .... thanx - have nice day ^_^ Good Luck!

mahilewets: 2017-08-20 13:26:18

So looks like test #15 is relatively big test


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