x,y 좌표로 나누어져 있는 지도의 각 중요 지점에다 정사각형 모양의 label 을 붙이려고 한다. 라벨은 아래 그림처럼 각 지점의 오른쪽 위나 아래 방향으로만 붙일 수 있다.

라벨의 크기는 가변적이지만, 지도에 쓰이는 라벨들의 크기는 같게 맞춰야 한다. 그리고 라벨들끼리 서로 붙어 있으면 안 된다. 이 때 가능한 한 라벨의 크기를 크게 정하고자 한다. 아래와 같은 지도가 있다면 , 이 지도에 붙일 수 있는 라벨의 최대 크기는 3 이다.

지도에 표시되어 있는 지점의 개수와 각 지점의 좌표가 입력으로 들어올 때, 라벨의 가능한 최대 크기를 구하는 프로그램을 작성하시오.

입력 형식

출력 형식

입출력 의 예

입력

6
3 12
8 10
11 9
6 5
9 5
5 3

출력

3

출처:ioi 기출