Programadores


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C#, C++, Python, Rust

Descripción

¡Sorprendentemente, Halk-E ha sido todo un éxito! Aunque todavía no hay una explicación lógica para este suceso, una compañía tiene a n programadores como candidatos a trabajar en la compañía, cada uno tiene un nivel de habilidad en Halk-E. De ellos se quieren seleccionar k pares de programadores para que trabajen en equipos, de tal forma que los niveles de habilidad de cada uno de los pares seleccionados sean lo más cercano posible, esto se debe a que la compañía cuenta con muy poco presupuesto aún.

Cuando un par de programadores con nivel de habilidades a y b son seleccionados se genera un costo de |a - b|. El costo total es la suma de los costos de todos los pares de programadores seleccionados.

Encuentra el menor posible costo total.

Entrada

La primera línea contiene dos enteros n y k: el número de programadores y el número de pares deseados.

La segunda línea contiene n enteros x_1, x_2, \dots, x_n representando el nivel de habilidad de cada programador.

Se asegura que 1 \le k \le \frac{n}{2}

Salida

Imprime un entero: el menor posible costo total.

Subtareas

  • Subtarea 1: 2 \le n \le 2000, 1 \le x_i \le 10^9 (34 puntos)
  • Subtarea 2: 2 \le n \le 2\cdot 10^5 , 1 \le x_i \le 1000 (21 puntos)
  • Subtarea 3: 2 \le n \le 2\cdot 10^5, 1 \le x_i \le 10^9 (45 puntos)

Ejemplos

Entrada 1
8 3
3 1 2 7 9 3 4 7
Salida 1
1

En este ejemplo, es posible seleccionar los pares de programadores con niveles de habilidades (1, 2), (3, 3) y (7, 7)


Comments

There are no comments at the moment.