Lanovka – The Cable Car

There are N peaks in the Vector Vista Mountains. We want to install cable car columns on K adjacent peaks so that if the largest height of the cable car (peak + column) is H, then on the other peaks the heights should be H – 1, H – 2, …, H – K + 1, so that the cable car continues to go up smoothly. The cable car always starts from the right and goes to the left.

We can achieve this by increasing the height of the cable car columns by 1 unit. By how many minimum units must the heights of columns be increased in total in order to create a cable car of length K?

Input Specification

The first line of the input contains the number of test cases T (1 ≤ T ≤ 20).

This is followed by two lines for each test case. The first line contains the number of peaks N (1 ≤ N ≤ 200 000) and the length of the cable car K (1 ≤ K ≤ N). The second line contains N natural numbers H_i (1 ≤ i ≤ N), the heights of the mountain peaks (1 ≤ H_i ≤ 1 000 000 000).

Output Specification

For each test case, print a single number on a line by itself: the minimum number of units.

Sample Input

1. 1
2. 5 3
3. 8 4 5 9 6

download as text file

Output for Sample Input

1. 4

download as text file

Explanation

The 3 possible cable cars are:

• Case 1: Peaks 5, 9, 6, with heights 10, 9, 8, and differences 5, 0, 2. The sum is 7.
• Case 2: Peaks 4, 5, 9, with heights 11, 10, 9, and differences 7, 5, 0. The sum is 12.
• Case 3: Peaks 8, 4, 5, with heights 8, 7, 6, and differences 0, 3, 1. The sum is 4.

The minimum of the total differences is 4.