1425번 - 원숭이 땅을 옮기다

원숭이는 나무에 산다. 원숭이의 나라는 2차원의 정수좌표로 나타낼 수 있다.

땅은 X축에 있고, 나무는 모두 X축의 정수좌표에 심어져 있다. 나무는 수직으로만 자라고, 이 나라에서 나무는 밑으로도 자란다.

원숭이는 나무에서 위아래로만 이동할 수 있다. 원숭이도 나무에서 떨어질 수 있기 때문에, 나무에서 나무로 점프하는 위험한 행동은 하지 않는다. 그리고 땅에서는 좌우로 이동하거나, 나무를 탈 수 있다.

원숭이들을 서로 다른 좌표에 위치해 있다. 원숭이들의 거리는 다음과 같이 구한다.

1. 만약 두 원숭이가 같은 X좌표에 있다면 (같은 나무에 있다면) 두 원숭이의 거리는 Y좌표의 차이이다. (파란색 그림)
2. 만약 두 원숭이가 다른 X좌표에 있다면 (다른 나무에 있다면) 두 원숭이의 거리는 땅과 원숭이 1 사이의 거리 + 땅과 원숭이 2 사이의 거리 + 그들의 X좌표의 차이 이다. (초록색, 분홍색 그림)

원숭이들의 왕 엔토피아는 원숭이들의 생활을 좀 더 편하게 해주기 위해서 땅을 옮기려고 한다.

엔토피아는 각 원숭이들의 거리의 최댓값을 최소화하려고 한다.

땅을 옮길때는 Y=N과 같이 X축에 수평인 방향으로만 옮길 수 있다. 땅을 옮기지 않을 수도 있다. 이때, N은 항상 정수이어야 한다.

원숭이의 위치가 주어졌을 때, 땅을 옮기거나 옮기지 않아서 원숭이들의 거리의 최댓값의 최솟값을 출력한다.

첫째 줄에 원숭이가 몇 마리 있는 지 주어진다. 원숭이는 적어도 2마리는 존재하며, 50마리를 넘지 않는다. 둘째 줄에 각 원숭이들의 좌표가 주어진다. 원숭이들의 좌표는 X좌표 Y좌표 순으로 주어진다. 좌표의 절댓값은 1,000,000,000보다 작거나 같다. 두 원숭이가 같은 위치에 있는 경우는 없다.

첫째 줄에 원숭이들의 거리의 최댓값의 최솟값을 출력한다.