ADAGROW  Ada and Replant
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 testcases.
The first line of each testcase contains two integers N, K 1 ≤ N ≤ 2000, 1 ≤ K ≤ 20
The next line contains N integers 0 ≤ A_{i} < 10^{4}, the costs of vegetables.
NOTE: The number of testcases varies depending on size of array (the longest array won't be a single file more than once).
Output
For each testcases, 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
TESTCASE1: 1 2 5 6 TESTCASE2: 1 2 5 7 11 TESTCASE3: 1 1 1 3 3 3 TESTCASE4: 1 2 1 2 6 5 6 5 TESTCASE5: 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:
20170910 09:38:41
@Min_25: Thank you! It means very much hearing this from you ^_^ 

Min_25:
20170909 21:55:15
Nice Problem ! 

morass:
20170821 12:43:19
@[Rampage] Blue.Mary: Good day to you,


[Rampage] Blue.Mary:
20170821 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:
20170820 22:32:49
@mahilewets: Can't access timus... oh good  seems its solved the ^^ 

mahilewets:
20170820 13:35:22
Oh yeah


mahilewets:
20170820 13:33:39
Really, my solution gives "4"


mahilewets:
20170820 13:28:59
Problem reminds of Bicolored Horses from Timus OJ


morass:
20170820 13:28:05
@mahilewets: Good day to you,


mahilewets:
20170820 13:26:18
So looks like test #15 is relatively big test 
Added by:  Morass 
Date:  20170819 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 