수영장 안전요원
시간 제한2초메모리 제한512 MB
주어진 N개의 시간 구간 중 정확히 하나를 제거한 뒤, 남은 구간들이 덮는 시간의 총 길이를 최대로 만드는 값을 구한다.
문제
농부 존은 젖소들이 쉬면서 우유를 더 많이 내도록 수영장을 열었다.
안전을 위해 젖소 마리를 안전요원으로 고용했다. 안전요원은 저마다 하루 중 연속된 시간 구간 하나를 담당한다. 수영장은 매일 시각 부터 시각 까지 열려 있으므로, 근무 구간 하나는 시작 시각과 끝 시각을 나타내는 두 정수로 적는다. 시각 에 근무를 시작해 시각 에 마치는 안전요원은 길이 3만큼의 시간을 담당한다. 시각은 길이가 없는 점이기 때문이다.
그런데 존은 급여를 감당할 수 있는 인원보다 한 명을 더 고용했다. 정확히 한 명을 해고해야 한다면, 남은 안전요원이 담당하는 시간의 합은 최대 얼마인가? 어떤 시간대는 안전요원이 한 명이라도 근무하고 있으면 담당된 것으로 본다.
입력
첫째 줄에 이 주어진다 ().
다음 개 줄에는 안전요원 한 명의 근무 시작 시각과 끝 시각이 두 정수로 주어진다. 두 값은 모두 이상 이하이고, 시작 시각이 끝 시각보다 작다. 입력에 나오는 개의 시각은 모두 서로 다르다. 서로 다른 안전요원의 근무 구간은 겹칠 수 있다.
출력
정확히 한 명을 해고한 뒤 담당되는 시간의 합이 최대 얼마인지 한 줄에 출력한다.