오로라

오늘 밤 드디어 오로라를 볼 기회가 왔다. 일주일 전부터 부모님을 졸라 저녁에 시골로 나가는 허락을 받았고, 두꺼운 옷을 입고 보온병에 뜨거운 커피를 담고 간단한 간식까지 챙겼다. 조건도 완벽해 보였다. 지평선에 구름 한 조각만 떠 있었으니 화려한 빛의 무늬를 기대할 만했다.

그런데 하늘을 볼 때마다 그 구름 한 조각이 하필 시선을 가로막았다. 이런 불운이 믿기지 않았고, 그날 밤에는 오로라를 한 번도 보지 못했다.

기분이 상한 채로 집에 돌아와 남은 시간이라도 자려고 했지만, 화가 나서 잠은 오지 않고 그 지긋지긋한 구름만 떠올랐다. 운이 지나치게 나빴다고 느낀 나는 마음을 가라앉히려고, 관측을 그렇게 완벽하게 방해하려면 구름이 최소 얼마나 컸어야 하는지 계산해 보기로 했다.

하늘은 실수 직선으로, 구름은 닫힌 구간으로 생각한다. 구름은 그 구간에 들어 있는 점을 모두 가린다. 구름의 속력은 어떤 순간에도 $1$ m/s를 넘지 못한다. 하늘을 볼 때마다 그 정확한 시각과 바라본 정확한 위치를 적어 두었다. 이 기록이 주어질 때, 오로라가 끝까지 가려져 있으려면 구름의 길이가 최소 얼마여야 하는지 구한다.

입력은 다음과 같이 주어진다.

• 첫째 줄에 하늘을 본 횟수를 나타내는 정수 $n$ ($1 \leq n \leq 3 \cdot 10^5$)이 주어진다.
• 이어지는 $n$개의 줄에는 각 관측의 시각과 위치를 나타내는 두 정수 $t$와 $x$ ($0 \leq t, x \leq 10^{12}$)가 주어진다.

입력에 주어지는 시각은 모두 서로 다르다.

오로라를 끝까지 보지 못하게 만드는 구름의 최소 길이를 출력한다. 답이 항상 정수임은 증명할 수 있다.