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 (1 \leq M \leq 50), el número máximo de tableros que pueden ser comprados; S (1 \leq S \leq 200), el número total de pesebreras; C (1 \leq C \leq S) el número de vacas en las pesebreras y los números de las C pesebreras ocupadas (1 \leq nrodepesebrera \leq S), 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.

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.