Рятувальники (Бронза)#10418
Фермер Джон відкрив для своїх корів басейн, розраховуючи, що це допоможе їм розслабитися й давати більше молока.
Щоб гарантувати безпеку, він наймає корів рятувальниками, кожна з яких має зміну, що покриває неперервний інтервал часу протягом дня. Для простоти вважаємо, що басейн відкритий щодня з моменту часу t = 0 до моменту часу t = 1000, тому кожну зміну можна описати двома цілими числами: моментами часу, коли корова починає та закінчує свою зміну. Наприклад, рятувальник, який починає в момент часу t = 4 і закінчує в момент часу t = 7, покриває три одиниці часу (зверніть увагу, що кінці інтервалу є "точками" в часі).
На жаль, Фермер Джон найняв на одного рятувальника більше, ніж може собі дозволити. Враховуючи, що він мусить звільнити рівно одного рятувальника, яку найбільшу кількість часу все ще можна покрити змінами решти рятувальників? Інтервал часу вважається покритим, якщо на ньому присутній хоча б один рятувальник.
Перший рядок містить ціле число n~(1 \le n \le 100). Кожен з наступних рядків описує рятувальника двома цілими числами в діапазоні від до : моментами початку та завершення зміни цього рятувальника. Усі ці моменти різні. Зміни різних рятувальників можуть перетинатися.
Виведіть одне ціле число: найбільшу кількість часу, яку все ще можна покрити, якщо Фермер Джон звільнить одного рятувальника.
Приклад 1