원숭이의 땅 옮기기

원숭이들은 2차원 정수 좌표로 표현되는 나라의 나무에서 산다. 땅은 x축과 평행한 한 직선이고, 모든 나무는 정수 x좌표에 심어진 수직선이다. 나무는 위쪽과 아래쪽으로 모두 이어져 있다.

원숭이는 나무 위에서는 위아래로만 움직일 수 있다. 나무에서 다른 나무로 직접 뛰어가지 않으며, 땅 위에서는 좌우로 이동하거나 나무를 오르내릴 수 있다.

두 원숭이의 거리는 다음과 같이 정의한다.

1. 두 원숭이의 x좌표가 같으면, 같은 나무에 있으므로 거리는 두 y좌표의 차이의 절댓값이다.
2. 두 원숭이의 x좌표가 다르면, 각 원숭이가 있는 위치에서 땅까지의 거리 두 개와 두 x좌표의 차이를 더한 값이다.

왕 엔토피아는 원숭이들이 더 편하게 지내도록 땅을 옮기려 한다. 땅은 Y = N 꼴의 수평선으로만 옮길 수 있고, 옮기지 않아도 된다. N은 정수여야 한다.

모든 원숭이 쌍의 거리 중 최댓값이 최소가 되도록 땅을 정했을 때, 그 최댓값을 구하라.

첫째 줄에 원숭이의 수 n이 주어진다. n은 2 이상 50 이하이다.

이후 입력에는 각 원숭이의 좌표 x y가 주어진다. 각 좌표의 절댓값은 1,000,000,000 이하이며, 두 원숭이가 같은 좌표에 있는 경우는 없다.

가능한 땅의 위치를 선택했을 때 모든 원숭이 쌍 거리의 최댓값이 가질 수 있는 최솟값을 출력한다.