균형

도시의 $N$ 명의 사람들이 각각 다른 위치 $(x_1, y_1) \ldots (x_N, y_N)$에 서 있습니다($1 \leq N \leq 1000$, 그리고 $x_i$와 $y_i$는 최대 $1,000,000$ 크기의 양의 홀수입니다). 도시 관리자는 도시를 분할하기 위해 긴 (실질적으로 무한한 길이의) 남북 방향의 울타리를 $x=a$ 방정식으로 건설하고자 합니다($a$는 짝수, 따라서 어떤 사람의 위치를 가로지르지 않도록 합니다). 그는 또한 긴 (실질적으로 무한한 길이의) 동서 방향의 울타리를 $y=b$ 방정식으로 건설하고자 합니다, 여기서 $b$는 짝수입니다. 이 두 울타리는 $(a,b)$ 지점에서 교차하며, 함께 그들의 도시를 네 지역으로 분할합니다.

도시 관리자는 네 개의 결과 지역에 나타나는 사람들이 합리적으로 "균형을 이루도록" $a$와 $b$를 선택하고자 합니다. 어느 지역도 너무 많은 사람을 포함하지 않도록 하기 위해. 네 지역 중 하나에 나타나는 사람의 최대 수를 $M$이라 하면, 도시 관리자는 $M$을 최대한 작게 만들고자 합니다. 그가 $M$의 최소 가능한 값을 결정하는 데 도움을 주세요.

입력의 첫 번째 줄에는 하나의 정수, $N$이 포함됩니다. 다음 $N$ 줄은 각각 하나의 사람의 위치를 지정하며, 그의 $x$와 $y$ 좌표를 명시합니다.

도시 관리자가 울타리의 위치를 최적으로 설정함으로써 달성할 수 있는 $M$의 최소 가능한 값을 출력해야 합니다.