Description

JOI 王国有 $N$ 位居民，编号从 $1$ 到 $N$。居民 $i$ ($1 \le i \le N$) 住在实数轴上的坐标 $X_i$ 处，其影响力为 $E_i$。可能有多个居民住在同一坐标处。拥有较大影响力的居民具有较高的广告潜力，但这样的居民在购买书籍时很谨慎。

Rie 出版了一本信息学的书。为了鼓励更多人购买这本书，她可以向一些居民赠送这本书的副本。如果她向居民 $i$ ($1 \le i \le N$) 赠送了一本书，居民 $i$ 将获得 Rie 的书。此外，在尚未获得书的居民中，满足以下条件的每位居民 $j$ ($1 \le j \le N$) 都会购买一本书并获得它。

• 居民 $i$ 和居民 $j$ 在实数轴上的距离小于或等于 $E_i - E_j$。换句话说，满足 $|X_i - X_j| \le E_i - E_j$。

如果所有居民都阅读了 Rie 的书，信息学奥林匹克将得到极大的认可。编写一个程序，计算需要向多少位居民赠送 Rie 的书，才能使 JOI 王国的所有居民都获得 Rie 的书。

Input Format

从标准输入读取以下数据。

$N$
$X_1$ $E_1$
$X_2$ $E_2$
$\vdots$
$X_N$ $E_N$

Output Format

向标准输出写入一行。输出应包含需要赠送 Rie 的书的最少居民数量，以便 JOI 王国的所有居民都获得 Rie 的书。

4
4 2
2 3
3 4
6 5

2

3
7 10
10 10
7 10

2

10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019

5

Hint

样例

样例 1

例如，如果 Rie 按以下方式赠送书，JOI 王国的所有居民将获得 Rie 的书。

• Rie 向居民 3 赠送了一本书。
  • 因为 $|X_3 - X_1| = 1$ 且 $E_3 - E_1 = 2$，居民 1 会购买一本 Rie 的书并获得它。
  • 因为 $|X_3 - X_2| = 1$ 且 $E_3 - E_2 = 1$，居民 2 会购买一本 Rie 的书并获得它。
  • 因为 $|X_3 - X_4| = 3$ 且 $E_3 - E_4 = -1$，居民 4 不会购买 Rie 的书。 因此，居民 1、2、3 将获得 Rie 的书。
• Rie 向居民 4 赠送了一本书。由于除了居民 4 之外的所有居民都已经获得了 Rie 的书，最终 JOI 王国的所有居民都获得了 Rie 的书。

由于不可能向少于两位居民赠送书以使 JOI 王国的所有居民都获得 Rie 的书，因此输出 2。

此样例输入满足子任务 2、3、4 的约束。

样例 2

此样例输入满足所有子任务的约束。

样例 3

此样例输入满足子任务 2、3、4 的约束。

约束

• $1 \le N \le 5 \times 10^5$。
• $1 \le X_i \le 10^9$ ($1 \le i \le N$)。
• $1 \le E_i \le 10^9$ ($1 \le i \le N$)。
• 给定值均为整数。

子任务

1. (10 分) $E_1=E_2=\cdots=E_N$。
2. (23 分) $N \le 16$。
3. (36 分) $N \le 10^3$。
4. (31 分) 无额外约束。

题面翻译由 ChatGPT-4o 提供。