도시 분리 timer 1s memory 512MB

N명의 시민은 각각 도시의 2차원 평면에서 서로 다른 위치 (x_1, y_1), ..., (x_N, y_N)에 살고 있다. (모든 시민의 위치는 짝수 정수로만 구성된다)

도시의 시장은 x=a라는 방정식을 가진 북-남 방향의 울타리를 세우고 싶어 한다. 여기서 a는 짝수 정수로 설정하여 사람들의 집을 허물지 않도록 한다. 그는 또한 y=b라는 방정식을 가진 동-서 방향의 울타리도 세우고 싶어 하는데, 여기서 b 역시 짝수 정수다. 이 두 울타리는 (a,b)라는 점에서 교차하며, 함께 도시를 네 개의 지역으로 나눈다.

시장은 적절한 두 정수 a와 b를 선택하여 네 개의 지역에 거주하는 시민의 수가 적절하게 "균형"을 이루도록 하고 싶다. 한 지역에 있는 시민의 수가 너무 많지 않도록 하기 위해 M을 정의하는데, 여기서 M은 네 개의 지역 중 가장 많은 시민이 살고 있는 지역의 시민의 수다. 시장은 M을 가능한 한 작게 만들기를 원한다. 최적의 울타리 위치를 찾아 시장이 달성할 수 있는 가장 작은 값 M을 계산하는 데 도움을 주자.