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:
20171004 01:15:23
@wcoders: Good day to you  maximum sum of N in single file is 2000 :) 

wcoders:
20171003 12:44:31
What is the maximum sum of N from all test cases in a single file ? 

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
[Deleted After AC.] Last edit: 20171019 06:16:49 

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

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