회전하지 않는 캘리퍼스

버니어 캘리퍼스는 기계 부품이나 사람의 신체 부위의 길이, 높이, 너비 등을 정밀하게 재는 자의 일종이다. 자 부분과 날 부분으로 구성되며, 두 날 사이에 물건을 끼워 너비를 잰다.

재휘는 알고리즘 수업에서 볼록 껍질에 쓰는 '회전하는 캘리퍼스' 알고리즘을 배웠다. 그런데 이 알고리즘을 그대로 따라 하던 재휘는 캘리퍼스를 껍질 주위로 돌리는 일이 매우 어렵다는 사실을 깨달았다. 그래서 재휘는 더 쉬운 회전하지 않는 캘리퍼스 알고리즘을 고안했다.

회전하지 않는 캘리퍼스 알고리즘은 다음과 같다. 먼저 한 평면 위에 점 $N$개가 주어진다. 다음으로 캘리퍼스를 점 집합과 같은 평면에 놓되, 자 부분이 $y$축과 평행하고 날 부분이 $x$축과 평행하도록 세운다. 그다음 날을 충분히 크게 벌린 뒤 조금씩 좁혀서, 날이 점에 닿으면 멈춘다. 캘리퍼스는 충분히 크게 벌린 상태에서 시작하며, 캘리퍼스가 측정한 거리 값이 실행 결과가 된다.

이제 회전하지 않는 캘리퍼스 알고리즘을 구현해 보자.

첫 번째 줄에 점의 수 $N$이 주어진다. 두 번째 줄부터 $N$개의 줄에 점들의 좌표 $x_i$, $y_i$가 공백으로 구분되어 주어진다. 점들의 좌표값은 모두 정수이다.

캘리퍼스로 측정한 거리 값을 출력한다.

• $3 \le N \le 2413$
• $-10^9 \le x_i, y_i \le 10^9 (1\le i \le N)$

2413은 재휘의 학번이다.