Socorristas (Platino)#10426
El granjero John abrió una piscina para sus vacas, pensando que esto les ayudaría a relajarse y dar más leche.
Para garantizar la seguridad, contrata a vacas como socorristas, cada una de las cuales trabaja en un turno que cubre un intervalo continuo de tiempo durante el día. Para simplificar, consideraremos que la piscina está abierta todos los días desde el instante hasta el instante 10^9, por lo que cada turno puede describirse mediante dos números enteros: los momentos de inicio y fin del turno de la vaca. Por ejemplo, un socorrista que comienza su turno en el instante t = 4 y lo termina en el instante t = 7 cubre tres unidades de tiempo (los extremos del turno representan instantes de tiempo).
Desafortunadamente, el granjero John contrató a socorristas más de los que puede permitirse pagar. Sabiendo que debe despedir exactamente a socorristas, ¿cuál es la cantidad máxima de tiempo que todavía pueden cubrir los turnos de los socorristas restantes? Se considera que un instante de tiempo está cubierto si al menos un socorrista está de guardia.
La primera línea contiene dos números enteros y k~(1 \le k \le 100, k \le n \le 10^5). Cada una de las siguientes líneas contiene dos números enteros s_i y t_i~(0 \le s_i < t_i \le 10^9) — los momentos de inicio y fin del turno del -ésimo socorrista. Todos los extremos de los turnos son distintos. Los turnos de distintos socorristas pueden superponerse.
Imprima la cantidad máxima de tiempo que todavía puede estar cubierto después de que el granjero John despida a socorristas.
Ejemplo 1
El granjero John debería despedir a los socorristas cuyos turnos son y .