11421142 SUSTech Online Judge
Problem 1142 --Joy’s New Job[Hard]

1142: Joy’s New Job[Hard]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 479  Solved: 71
[Submit][Status][Web Board]


Macau casino has a popular game: horse racing. However, the rule is different from the normal ones. It is about  guessing the kth fastest horse. Joy wants to apply a job in the casino, but his boss give him a test. He can get the job only if he passes the test. The rules are as followed:

Given the strength of n horses, (to simplify, the strength of the n horses is a permutation of 1 to n, and horse with larger strength run faster), the boss wants to know the sum of all the kth fastest horse in every consecutive interval of the n horses, and remember only the intervals equal or longer than k should be considered.

Joy is not good at math, so he turns to you for help.


There is only one integer T (1 <= T <= 10) in the first line, denoting the number of test cases.

For each test case, the first line includes two integers n and k. k <= min(n, 80), the sum of n in all test cases does not exceed 5 * 105. The second line is the strength of the n horses.


For each test case, output a line containing the answer.

Sample Input

5 2
1 2 3 4 5

Sample Output