P3138 [USACO16FEB] Load Balancing S

*This problem has the same statement as the [problem with the same name in the Platinum division](/problem/P6172); the only difference is in the constraints.*

Farmer John has $N$ cows ($1 \leq N \leq 1000$) scattered across his farm. The farm is an infinite 2D plane, and the $i$-th cow is located at $(x_i, y_i)$ (it is guaranteed that $x_i$ and $y_i$ are positive odd integers, and $x_i, y_i \leq 10^6$). No two cows are at the same position. FJ wants to build a vertical fence with equation $x = a$, and a horizontal fence with equation $y = b$. To ensure the fences do not pass through any cow, both $a$ and $b$ must be even. It is easy to see that these two fences intersect at $(a, b)$, partitioning the farm into four regions. FJ wants the number of cows in the four regions to be as balanced as possible, avoiding the situation where one region has many cows while another has few. Let $M$ be the maximum number of cows among the four regions. Please help FJ find the minimum possible value of $M$.

The first line contains an integer $N$. The next $N$ lines each contain two integers $x_i, y_i$, describing the position of the $i$-th cow.

Output the minimum possible value of $M$.

Translated by ChatGPT 5