시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 343 188 154 56.410%

문제

선물 포장 공장을 말아먹은 욱제는 계곡에서 백숙을 파느라 학교에 자주 가지 못한다. 하지만 월클의 인생은 피곤한 법! 욱제는 지금처럼 힘든 시기에도 자신을 기다리는 5조5억명의 열렬한 팬들을 위해 가끔씩 학교에 가 줘야 한다. 욱제는 백숙이 끓는 걸 지켜봐야 해서 가게를 오래 비울 수 없다. 그래서 욱제는 한 번 학교에 간 뒤 최소 시간동안 머물다가 모든 팬들과 한 번씩 인사를 하고 학교를 떠나려고 한다.

욱제는 임의의 시각에 학교에 오거나 학교를 떠날 수 있고, 단 한 번의 왕복만 한다. 동시에 여러 팬들에게 인사를 끝낼 수도 있다. 욱제는 잘생겨서 인사하면 팬들이 심쿵사로 바로 쓰러지기 때문에 인사를 하는데 소요되는 시간은 0이라고 하자.

<그림 1>

예를 들어 3명의 팬 A, B, C가 학교에 머무르는 시간이 <그림 1>과 같다고 하자. 이 경우 시각 2에 3명의 팬이 모두 학교에 있으므로, 욱제는 시각 2에 학교에 와서 3명에게 동시에 인사를 하고 바로 가게로 돌아갈 수 있다. 시각 3이나 4도 마찬가지이다. 이때 욱제가 학교에 머무는 시간의 총합은 0이다.

<그림 2>

다른 예로 2명의 팬 A와 B가 학교에 있는 시간이 <그림 2>와 같다고 하자. 욱제는 시각 4부터 시각 5까지 학교에 머물면서 시각 4에 A와, 시각 5에 B와 인사를 하고 학교를 떠날 수 있다. 이때 욱제가 학교에 머무는 시간은 1이다.

백숙집 주방 이모 효빈이는 N명의 팬들이 학교에 머무르는 시간 [s, e]들을 몰래 조사했다. 효빈이는 욱제가 학교에 머무르는 시간을 계산해서 그 시간동안 땡땡이를 치기로 했다. 효빈이와 함께 욱제가 학교에 머무르는 최소의 시간을 계산해 보자!

입력

첫째 줄에 욱제의 열렬한 팬의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에 걸쳐, 각 줄에 정수 si, e(1 ≤ si ≤ ei ≤ 100,000)가 순서대로 주어진다. 이는 i번째 팬이 학교에 있는 시간 [si, ei]을 의미한다.

출력

욱제가 학교에 머물러야 하는 최소의 시간을 출력한다.

예제 입력 1

3
2 5
1 4
2 4

예제 출력 1

0

예제 입력 2

2
1 4
5 6

예제 출력 2

1

출처

University > 숭실대학교 > 2019 SCON F번