Socorristas (Plata)#10420
El granjero John abrió una piscina para sus vacas, con la esperanza de que esto les ayude a relajarse y a dar más leche.
Para garantizar la seguridad, contrata a vacas como socorristas, cada una de las cuales tiene 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 momento t = 0 hasta el momento t = 10^9, por lo que cada turno puede describirse mediante dos números enteros: los momentos en que la vaca comienza y termina su turno. Por ejemplo, un socorrista que comienza a trabajar en el momento t = 4 y termina en el momento t = 7 cubre tres unidades de tiempo (nótese que los extremos del intervalo son "puntos" en el tiempo).
Desafortunadamente, el granjero John contrató a un socorrista más de los que puede permitirse. Sabiendo que debe despedir exactamente a un socorrista, ¿cuál es la mayor cantidad de tiempo que puede quedar cubierta por los turnos de los socorristas restantes? Se considera que un intervalo de tiempo está cubierto si hay al menos un socorrista de guardia.
La primera línea contiene un número entero n~(1 \le n \le 10^5). Cada una de las siguientes líneas describe a un socorrista mediante dos números enteros en el rango de a 10^9: los momentos de inicio y fin del turno de ese socorrista. Todos estos momentos son distintos. Los turnos de diferentes socorristas pueden superponerse.
Muestre un único número entero: la mayor cantidad de tiempo que puede quedar cubierta si el granjero John despide a un socorrista.
Ejemplo 1