题目描述

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$.

5
0 9999
0 0
0 -9999
200 0
10000 9999

2

5
10 -9999
0 0
3 9999
9000 -9999
10003 9999

2

6
10 -9999
0 0
3 9999
9000 -9999
10003 -9999
10003 9999

3