#C7933. Minimum Operations to Maximize Consecutive Sum

    ID: 51859 Type: Default 1000ms 256MiB

Minimum Operations to Maximize Consecutive Sum

Minimum Operations to Maximize Consecutive Sum

You are given an array of n integers and an integer m. You are allowed to perform swap operations (swapping any two elements) arbitrarily many times. Your goal is to arrange the elements such that the sum of any m consecutive elements is maximized.

The maximum possible sum for any m consecutive segment is given by \[ S_{max} = \sum_{i=1}^{m} a_i^* \] where \(a_1^*, a_2^*, \dots, a_m^*\) are the m largest elements in the array. Note: Since you can perform swaps arbitrarily to cluster these m largest numbers together, it is always possible to achieve this configuration without performing any operations, hence the answer is always 0.

For example, consider the test case:

Input:
4 2
1 -3 4 5

The two largest numbers are 5 and 4, whose sum is 9. It is always possible to rearrange the array so that they are consecutive using 0 operations. Therefore, the answer for this test case is 0.

</p>

inputFormat

The first line contains an integer t (1 ≤ t ≤ 104), the number of test cases.

For each test case:

  • The first line contains two integers n and m (1 ≤ m ≤ n ≤ 105).
  • The second line contains n integers separated by spaces.

It is guaranteed that the total sum of n over all test cases does not exceed 106.

outputFormat

For each test case, output a single line containing one integer — the minimum number of operations required to rearrange the array so that the sum of any m consecutive elements is maximized.

Note: In this problem, as explained in the description, the answer is always 0.

## sample
5
4 2
1 -3 4 5
5 3
-1 -2 -3 -4 -5
3 1
99 100 101
5 2
1 2 3 4 5
6 3
5 -6 4 -3 2 -1
0

0 0 0 0

</p>