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
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

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

Something like WA14 or WA15.


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