(Examen clasificatorio de la Olimpiada de Informática CDMX-EDOMEX ciclo 21-22 Nivel 02 Día 1 Problema 2)

Descripción

En la CDMX hay una enorme calle en forma de círculo que mide exactamente $1,000,000$ unidades de circunferencia. Existen $N$ casas en la calle cuya dirección es su posición en la circunferencia siguiendo el orden de las manecillas del reloj desde el punto norte de la calle. Este punto tiene la dirección $0$.

Los bomberos de la ciudad quieren ampliar su cobertura contra incendios en la calle, por lo que han decidido establecer $K$ hidrantes (hidrante es una bomba de agua, normalmente de color rojo, donde los bomberos conectan las mangueras) en direcciones enteras de la circunferencia. Además, es posible colocar hidrantes en la misma dirección que una casa. La distancia de un hidrante a una casa es la diferencia absoluta entre sus direcciones. Por ejemplo, un hidrante colocado en la dirección $7$ está a distancia $3$ de la casa con dirección $4$ y a distancia $5$ de la casa con dirección $12$. Por supuesto, un hidrante en la dirección $0$ está a distancia $1$ de las casas con dirección $1$ y $999,999$.

Todas las mangueras que utilizan los bomberos son de una sola y única longitud (o sea, todas las mangueras miden lo mismo). El cuerpo de bomberos desea tener todas las casas de la calle al alcance de sus hidrantes. Con el fin de que cada casa esté cubierta por al menos un hidrante. Los bomberos quieren designar sus posiciones de tal manera que la longitud requerida de las mangueras sea tan pequeña como sea posible.

Problema

Dada la cantidad $N$ de casas existentes en la calle y la cantidad $K$ de hidrantes que se van colocar en la calle, determina la longitud mínima de las mangueras de tal manera que cada casa esté cubierta por al menos un hidrante.

Entrada

En la primera el entero $N(1\le N\le {10}^3)$, la cantidad de casas de la calle.
En las siguientes $N$ líneas, las direcciones de todas las casas. Puedes asumir que cada casa tiene una dirección diferente.
En la última línea, el entero $K(1\le K\le {10}^3)$, la cantidad de hidrantes a colocar.

Salida

Un valor entero con la longitud mínima que deben tener todas las mangueras para poder cubrir las casas.

Ejemplo A

Entrada

4
0
25
30
40  
2

Salida

8

Explicación.- Podemos colocar los hidrantes en las posiciones $0$ y $32$, consiguiendo que el hidrante en 0 cubra la casa en la posición $0$ y el hidrante en $32$ alcance las casas en las posiciones $25$, $30$ y $40$.

Ejemplo B

Entrada

4
1
2
3
4
1

Salida

2

ExplicaciónUn solo hidrante en la posición $2$ y con manguera de longitud $2$ puede cubrir a todas las casas.

Subtareas

Subtarea 1 con un valor de 10 puntos: N = 2, K = 1.
Subtarea 2 con un valor de 20 puntos: N ≤ 100, K = 1.
Subtarea 3 con un valor de 30 puntos: N ≤100, K ≤ 100
Subtarea 4 con un valor de 40 puntos: (1 ≤ N ≤ 10^3) y (1 ≤ K ≤ 10^3).

NOTA:

Cada subtarea contiene un conjunto de casos de prueba, se te darán los puntos siempre y cuando tu programa resuelva todos los casos de la subtarea.