training.py

'''
Problem
As the football coach at your local school, you have been tasked with picking a team of exactly P students to represent your school. There are N students for you to pick from. The i-th student has a skill rating Si, which is a positive integer indicating how skilled they are.

You have decided that a team is fair if it has exactly P students on it and they all have the same skill rating. That way, everyone plays as a team. Initially, it might not be possible to pick a fair team, so you will give some of the students one-on-one coaching. It takes one hour of coaching to increase the skill rating of any student by 1.

The competition season is starting very soon (in fact, the first match has already started!), so you'd like to find the minimum number of hours of coaching you need to give before you are able to pick a fair team.

Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing the two integers N and P, the number of students and the number of students you need to pick, respectively. Then, another line follows containing N integers Si; the i-th of these is the skill of the i-th student.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of hours of coaching needed, before you can pick a fair team of P students.
'''

# coding:utf-8

t = int(raw_input())

for tc in xrange(t):
    n, p = map(int, raw_input().split())
    # Recebe-se o array de skills e já o ordena (complexidade O(nlogn)).
    s = sorted(map(int, raw_input().split()))
    
    # Os índices l (left) e r (right) servem para indicar o início
    # e o fim do subarray que estiver sendo analisado por vez.
    l = 0
    r = p - 1

    # A soma total de horas de treinamento de um subarray é dada pela
    # soma das diferenças do maior elemento (que está no índice r) por
    # cada um dos demais elementos do array. Armazena-se o valor do
    # primeiro subarray numa variável chamada curr_sum. Complexidade O(p).
    curr_sum = 0

    for i in xrange(r):
        curr_sum += s[r] - s[i]

    # O min_sum vai servir para guardar a menor soma das diferenças dos
    # subarrays do array de habilidades.
    min_sum = curr_sum

    # Aumenta-se l e r a cada iteração, considerando o próximo subarray
    # possível de tamanho p. A principal minúcia é o cálculo do novo valor
    # de curr_sum.
    # Vamos considerar um exemplo:
    #   Sejam s = [a, b, c, d, e, f...] e p = 4.
    #   Os valores iniciais de l e r são 0 e 3, respectivamente, considerando
    #   assim o subarray [a, b, c, d]. Aqui, temos que
    #       curr_sum = d - a + d - b + d - c.
    #   O próximo subarray está compreendido entre os índices 1 e 4. Assim, o
    #   novo subarray é [b, c, d, e]. Daí, sabemos que o novo valor esperado é
    #       curr_sum' = e - b + e - c + e - d. 
    #   Dispondo desses valores, podemos avaliar a diferença X entre curr_sum e
    #   curr_sum':
    #       curr_sum + X = curr_sum'
    #       X = curr_sum' - curr_sum
    #         = e - b + e - c + e - d - (d - a + d - b + d - c)
    #         = (p - 1) * e - b - c - d - [(p - 1) * d - a - b - c]
    #         = (p - 1) * e - b - c - d - (p - 1) * d + a + b + c
    #         = (p - 1) * e - d - (p - 1) * d + a
    #         = (p - 1) * e - d + (1 - p) * d + a
    #         = (p - 1) * e + (1 - p - 1) * d + a
    #         = (p - 1) * e - p * d + a
    #   Nota-se que, independentemente do tamanho de p, a manutenção de valores
    #   só é feita a partir dos valores de três elementos do array: os que
    #   estavam nos valores anteriores de l e r (nesse caso, 'a' e 'd') e o novo
    #   valor em r ('e').
    #   Resumindo: a cada iteração, em relação a curr_sum:
    #       1) soma-se o valor mais à esquerda anterior;
    #       2) subtrai-se p vezes o valor mais à direita anterior;
    #       3) soma-se o novo valor mais à direita p - 1 vezes. 
    #   No fim das contas, essa operação tem uma complexidade O(n - p).
    while l <= r <= n - 2:
        l += 1
        r += 1
        curr_sum += (p - 1) * s[r] + s[l - 1] - p * s[r - 1]
        min_sum = min(curr_sum, min_sum)

    print 'Case #{}: {}'.format(tc + 1, min_sum)