avoid-boredom

Exams are approaching soon and everyone tries to get ready for them.  So, Omar decides to begin studying his subjects. He has N subjects and he wants to study M of them today. According to Omar, every subject has an interest level, A_i which indicates how much Omar likes that subject. Unfortunately, Omar feels bored easily, so he decides to choose a collection of interesting and boring subjects. Actually, Omar wants to choose M subjects such that the summation S of the absolute difference between every two adjacent subjects' interest levels is maximum as possible. Omar will put the selected M subjects in a group in the same order as described in the input, and then he will proceed to calculate S.  

Please help Omar and rescue him from boredom

Input:

First line of the input contains an integer T denoting the number of test cases. 
First line of every test-case contains two space separated integers N and M.   
Second line of every test case contains N space separated integers A_i denoting the interest level for i^{th} subject. 

*Output: *

For each case, print the above described S in a separate line.  

Constraints:

1 ≤ N ≤ 100.
1 ≤ M ≤ N.
1 ≤ A_i ≤ 10^{9}

SAMPLE INPUT
1
5 3
100 50 3000 4000 40

SAMPLE OUTPUT
7910

Explanation

You should choose the following group (50,4000,40) in the same order that appears in the input. S = |50-4000|+|4000-40| = 7910.

Source: hackerearth | Difficulty: EASY
Tags: Dynamic programming

Complete search


Solutions: