안전요원

시간 제한2초메모리 제한512 MB

요약

N개의 근무 구간 중 하나를 제거했을 때 남은 구간들이 덮는 총 시간의 최댓값을 구한다.

난이도: 쉬움10점 중 3점
유형: 구간, 완전 탐색, 배열
정답자: 아직 제출이 없습니다

문제

존 농부가 젖소를 위해 수영장을 열었다. 젖소가 쉬면서 우유를 더 많이 내기를 바라기 때문이다.

안전을 위해 존 농부는 젖소 $N$ 마리를 안전요원으로 고용했고, 각 젖소는 하루 중 연속된 한 구간을 맡는다. 수영장은 매일 시각 $t=0$ 부터 시각 $t=1000$ 까지 문을 열기 때문에, 각 근무는 정수 두 개, 즉 근무를 시작하는 시각과 끝내는 시각으로 나타낼 수 있다. 예를 들어 시각 $t=4$ 에 시작해 시각 $t=7$ 에 끝나는 안전요원은 시간 3단위를 맡는다. 시각은 점이고, 근무의 길이는 끝 시각에서 시작 시각을 뺀 값이다.

그런데 존 농부는 예산으로 감당할 수 있는 인원보다 안전요원을 한 명 더 고용했다. 정확히 한 명을 해고해야 할 때, 남은 안전요원의 근무가 덮는 시간의 최댓값은 얼마인가? 어떤 시간은 안전요원이 한 명이라도 있으면 덮인다.

입력

첫 줄에 $N$ 이 주어진다 ( $1 \leq N \leq 100$ ). 다음 $N$ 개 줄에는 안전요원 한 명의 근무가 정수 두 개로 주어지며, 각각 근무의 시작 시각과 끝 시각이다. 두 값은 모두 $0$ 이상 $1000$ 이하이고, 시작 시각은 끝 시각보다 작다. 입력에 나오는 시각 $2N$ 개는 모두 서로 다르다. 서로 다른 안전요원의 근무는 겹칠 수 있다.

출력

존 농부가 안전요원 한 명을 해고한 뒤에도 덮을 수 있는 시간의 최댓값을 한 줄에 정수 하나로 출력한다.

예제3

예제 1
입력
```
3
5 9
1 4
3 7
```
예상 출력
```
7
```
예제 2
입력
```
2
0 1000
400 600
```
예상 출력
```
1000
```
예제 3
입력
```
3
10 40
41 70
71 99
```
예상 출력
```
59
```