Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4096

Time Limit: 1 Second      Memory Limit: 65536 KB

$N$ letters have just arrived at the post office positioned at $x = 0$, and the $i$-th letter should be posted to position $x = a_i$. BaoBao, our beloved postman, will start his work from the post office and deliver all these letters by himself.

Unfortunately, BaoBao's backpack can only hold at most $K$ letters each time (which means that if he wants to deliver some letter not in his backpack, he will have to go back to the post office and fetch it), so he may not be able to deliver all $N$ letters in one go. Please note that BaoBao cannot temporarily drop a letter outside the post office and pick it back afterward.

What's the minimum distance BaoBao has to travel to deliver all $N$ letters?

It's NOT necessary that BaoBao ends his delivery in the post office.


There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $N$ and $K$ ($1 \le K \le N \le 10^5$), indicating the total number of letters and the capacity of the backpack.

The second line contains $N$ integers $a_1, a_2, \dots, a_N$ ($-10^9 \le a_i \le 10^9$), indicating the destination of each letter.

It's guaranteed that the sum of $N$ over all test cases will not exceed $10^6$.


For each test case output one line containing one integer, indicating the minimum distance BaoBao has to travel to deliver all the letters, starting from the post office at $x = 0$.

Sample Input

5 3
-1 -2 3 -4 -5
6 3
1 0 -2 -1 1 2

Sample Output



For the first sample test case, BaoBao can first deliver the 1st and the 3rd letter (go to $x = 3$, then to $x = -1$, then to the post office), then deliver the 2nd, the 4th and the 5th letter (go to $x = -2$, then to $x = -4$, then to $x = -5$), and ends his delivery at $x = -5$.

Author: WENG, Caizhi
Source: The 19th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status