Matcom Online Grader

La creación del horario de los turnos de clase en la facultad siempre es bastante difícil porque hay que tener en cuenta múltiples parámetros, como la cantidad de aulas, el hecho de que los profesores pueden dar varios turnos y otros cuestiones similares. Después de mucho trabajo se logró hacer un horario para el nuevo curso pero nos topamos con un problema imprevisto. Debido a las acciones de mantenimiento que se están haciendo en la facultad hay un grupo de aulas que no pueden ser utilizadas. Como volver a hacer el horario implica mucho trabajo, se decidió que lo mejor es usar todas las aulas que se tienen disponibles y mandar a otras facultades a los estudiantes que no podemos acomodar. Para esto lo que se hizo fue decidir que turnos se darán en la facultad y enviar el resto a otras facultades. Como esta solución implica que los estudiantes se deben mover entre una facultad y otra, se quiere que la cantidad de turnos que no se den en nuestra facultad sea la menor posible para minimizar las molestias ocasionadas. Por supuesto los turnos que demos en la facultad deben poderse asignar cada uno a un aula de forma que no ocurran dos turnos distintos al mismo tiempo en la misma aula. Podemos asumir que el tiempo entre que acaba un turno y el aula esta lista para ser usada es cero. Dados la hora de inicio y de fin de cada curso y la cantidad de aulas que podemos usar se quiere calcular la menor cantidad de turnos que deben darse en otras facultades.

La primera línea de la entrada contiene dos enteros $N$ ($1 \leq N \leq 600$) y $M$ ($1 \leq M \leq 1000$) que son la cantidad de turnos y la cantidad de aulas disponibles respectivamente. Le siguen $N$ líneas cada una describe un turno de clase con dos enteros $A$ y $B$ que son la hora de inicio y de fin, donde $1 \leq A \lt B \leq 10000$.