P14773 [ICPC 2024 Seoul R] Square Stamping

In the plane, there are $ n $ points whose y-coordinates are either $ -9999 $, $ 0 $, or $ 9999 $. Let $ P $ be the set of these $ n $ points. Your task is to enclose all the points in $ P $ by a minimum number of congruent axis-parallel squares of side length 10,000. As a subset of the plane, each such square consists of all points inside and on the boundary.

Your program is to read from standard input. The input starts with a line consisting of a single integer $ n $ ($ 1 \leq n \leq 300,000 $), representing the number of input points in $ P $. In each of the following $ n $ lines, there are two integers $ x $ and $ y $, representing the $ x $- and $ y $-coordinates of a point in $ P $, respectively, such that it holds that $ -10^9 \leq x \leq 10^9 $ and $ y \in \{-9999, 0, 9999\} $. You may assume that all the $ n $ input points are distinct.

Your program is to write to standard output. Print exactly one line. The line should consist of a single integer that represents the minimum possible number $ t $ such that there exist $ t $ axis-parallel squares of side length 10,000 whose union encloses all the input points in $ P $.