Reparación del Establo.


Submit solution

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

Author:
Problem type

Fue una noche oscura y tormentosa que arrancó el techo y las puertas de las pesebreras donde estaban las vacas del Granjero Juan. Afortunadamente, muchas de las vacas estaban de vacaciones, por lo tanto el establo no estaba totalmente lleno.

Las vacas pasan la noche en pesebreras que están dispuestas adyacentes unas a las otras en una lìnea larga. Algunas pesebreras tienen vacas en ellas; algunas no. Todas las pesebreras tienen la misma longitud.

El Granjero Juan debe erigir rápidamente nuevos tableros en la parte frontal de los establos, pues se perdieron las puertas. Su nuevo proveedor de leña le dará tableros de cualquier largo que él desee, pero el proveedor puede únicamente llevar un pequeño número de tableros en total. El granjero Juan quiere minimizar la longitud total de tableros que él debe comprar.

Dados M, el número máximo de tableros que pueden ser comprados; S, el número total de pesebreras; C el número de vacas en las pesebreras y los números de las C pesebreras ocupadas, calcule el mínimo número de pesebreras que deben ser bloqueadas con el fin de bloquear todas las pesebreras que tienen vacas en ellas.

Entrada

  • Línea 1: M, S, y C (separados entre sí por un espacio).
  • Lìneas 2-C+1: Cada línea contiene un número, los números de las pesebreras ocupadas.

Salida

Una sola línea con un entero que representa el número total de pesebreras bloqueadas.

Restricciones

  • 1 \leq M \leq 50
  • 1 \leq S \leq 200
  • 1 \leq C \leq S
  • 1 \leq nrodepesebrera \leq S

Ejemplo de Entrada

4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

Ejemplo de Salida

25

Explicación de la Salida: Un arreglo mínimo es un tablero cubriendo las pesebreras 3-8, uno cubriendo 14-21, uno cubriendo 25-31, y uno cubriendo 40-43.


Comments

There are no comments at the moment.