28a Olimpíada Brasileira de Informática
Submeta sua solução

Trio de Bonecas

Alice é a gerente de produção de uma fábrica de bonecas chinesas. Nessa fábrica, todas as bonecas possuem o mesmo formato, variando apenas de tamanho. As bonecas são vendidas sempre em trios.
Para um trio formado por bonecas de tamanhos A, B e C, com A ≤ B ≤ C, o balanceamento do trio é definido como (A - B)^2. De acordo com o controle de qualidade da fábrica, idealmente cada trio deveria ter balanceamento 0, ou seja, conter duas bonecas de mesmo tamanho e uma terceira boneca de tamanho maior ou igual a essas duas; porém, isso nem sempre é possível devido a limitações de estoque. Alice acabou de receber um pedido urgente: o consulado Chinês fará um grande evento no qual pretende distribuir K trios de bonecas, e precisa que Alice envie imediatamente todos os trios. Existem na fábrica N bonecas de diversos tamanhos, ainda não separadas em trios, e Alice não sabe se conseguirá formar K trios ideais. Devido à urgência do evento, Alice e o consulado fizeram um acordo: o consulado aceitará trios que não sejam ideais; porém, para garantir um bom evento, Alice deve enviar uma caixa com K trios de bonecas cuja soma dos balanceamentos seja a menor possível. Por exemplo, suponha que Alice possua 7 bonecas com tamanhos 11, 1, 7, 5, 16, 8 e 15, e que o consulado tenha solicitado 2 trios de bonecas. Algumas configurações possíveis para envio são:
  • Configuração 1: trios (7, 8, 15) e (1, 5, 16).
    • O primeiro trio possui balanceamento (8 - 7)^2 = 1.
    • O segundo trio possui balanceamento (5 - 1)^2 = 16.
    • O balanceamento total dessa configuração é 1 + 16 = 17.
  • Configuração 2: trios (5, 7, 16) e (8, 11, 15).
    • O primeiro trio possui balanceamento (7 - 5)^2 = 4.
    • O segundo trio possui balanceamento (11 - 8)^2 = 9.
    • O balanceamento total dessa configuração é 4 + 9 = 13.
Existem outras configurações possíveis, mas a menor soma de balanceamentos possível é 13 (correspondente à configuração 2). Ajude Alice a calcular a soma de balanceamentos minima em um conjunto com K trios de bonecas.

Entrada

A primeira linha de entrada contém dois inteiros N e K, representando, respectivamente, o número de bonecas e a quantidade de trios solicitados pelo consulado Chinês. A segunda linha contém N números inteiros. O i-ésimo desses números será Ti, representando o tamanho da i-ésima boneca.

Saída

Seu programa deverá imprimir uma única linha contendo um único inteiro, a menor soma de balanceamentos possível em uma caixa com K trios de bonecas.

Restrições

  • 3 ≤ N ≤ 10 000
  • 1 ≤ K ≤ 3 000
  • 3 K ≤ N
  • 1 ≤ Ti ≤ 100 000 para todo 1 ≤ i ≤ N

Informações sobre a pontuação

A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:
  • Subtarefa 1 (13 pontos): 1 ≤ Ti ≤ 2 para todo 1 ≤ i ≤ N.
  • Subtarefa 2 (28 pontos): N ≤ 30.
  • Subtarefa 3 (33 pontos): N ≤ 1 000 e K ≤ 100.
  • Subtarefa 4 (26 pontos): Nenhuma restrição adicional.
Seu programa pode resolver corretamente todas ou algumas das subtarefas acima (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por qualquer uma das suas submissões.

Exemplos

Entrada
7 2
11 1 7 5 16 8 15
Saída
13
	

 

Entrada
8 2
2 1 2 2 2 1 2 2
Saída
0
	

 

PJ P1 P2 PS
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação