← 返回题目列表

Codeforces · 1533/J

J. 棋子

中文机器翻译题面 查看原题

有一个无限的棋盘,分为多个单元格。单元格 $$$(x, y)$$$ 是第 $$$x_i$$$ 行和 $$$y_i$$$ 列的交集处的单元格。 $$$n$$$ 个黑色棋子被放置在棋盘上,第 $$$i$$$ 个黑色棋子占据单元格 $$$(x_i, y_i)$$$。

你想吃掉所有黑色棋子。为此,您可以执行以下操作:

- 将一个白色棋子放入任何空单元格中(可以选择具有整数坐标的任何单元格,只要它不包含任何棋子);
- 根据国际象棋规则用白棋之一走棋。

回想一下,当您在单元格 $$$(x, y)$$$ 中使用白棋移动时,国际象棋规则允许您选择以下操作之一:

- 如果单元格$$$(x + 1, y - 1)$$$中有一个黑色棋子,你可以捕获它——黑色棋子从棋盘上移除,白色棋子移动到$$$(x + 1, y - 1)$$$;
- 如果单元格$$$(x + 1, y + 1)$$$中有一个黑色棋子,你可以捕获它——黑色棋子从棋盘上移除,白色棋子移动到$$$(x + 1, y + 1)$$$;
- 如果单元格 $$$(x + 1, y)$$$ 为空,您可以将白色棋子移动到该单元格。

你可以执行任何有限的动作序列(放置白色棋子并移动它们)。你想要吃掉所有的黑棋子,并且可以证明这总是有可能的;并且你想要放置尽可能少的白色棋子。

要捕获所有 $$$n$$$ 黑色棋子,您必须放置最少数量的白色棋子?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 黑棋子的数量。

然后是 $$$n$$$ 行。第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le 5 \cdot 10^5$$$) 表示单元格 $$$(x_i, y_i)$$$ 中的一个黑色棋子。没有单元格被两个或更多黑色棋子占据。

输出

打印一个整数 — 为捕获所有 $$$n$$$ 黑色棋子而必须放置的白色棋子的最小数量。

示例

输入 #1

3
1 1
5 1
2 2

输出 #1

1

输入 #2

3
3 2
1 3
1 1

输出 #2

2

输入 #3

2
1 1
2 2

输出 #3

1