题目描述

有 $10^9 \times 10^9$ 个格子按正方形排列，编号从 $(1, 1)$ 到 $(10^9, 10^9)$。格子 $(i, j)$ 表示从上往下第 $i$ 行，从左往右第 $j$ 列的格子。最初，有 $N$ 个格子 $(x_1, y_1), \ldots, (x_N, y_N)$ 是黑色，其余所有格子都是白色。

すぬけ君可以进行如下操作任意次：

• 选择整数 $x\ (1 \leq x \leq 10^9 - 1)$ 和整数 $y\ (1 \leq y \leq 10^9 - 2)$，将 $6$ 个格子 $(x, y), (x, y+1), (x, y+2), (x+1, y), (x+1, y+1), (x+1, y+2)$ 的颜色反转（黑变白，白变黑）。

请计算经过若干次操作后，黑色格子的数量可能达到的最小值。

输入格式

输入从标准输入读入，格式如下：

$N$
$x_1\ y_1$
$\vdots$
$x_N\ y_N$

输出格式

请输出答案。

样例 1

输入

9
1 2
1 3
2 1
2 3
2 4
3 2
3 3
3 4
4 2

输出

3

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq x_i, y_i \leq 10^9$
• $(x_i, y_i)$ 互不相同。
• 输入中的所有值都是整数。

样例解释 1

下图中，从上到下第 $i$ 个字符串的第 $j$ 个字符表示格子 $(i, j)$。# 表示黑色，. 表示白色。

.##.
#.##
.###
.#..
-> 
#...
.#.#
.###
.#..
-> 
#...
..#.
....
.#..

由 ChatGPT 4.1 翻译