第 2 题 宣传 2 (advertisement2)

CSP-S 复赛模拟赛 26 · 时间限制 1.0 s · 空间限制 256 MB · 41 个测试点 · 全文比较（过滤行末空格及文末回车）

配点：100 点 时间限制 / 内存限制：原文未标注

本题使用文件输入输出：输入文件 advertisement2.in，输出文件 advertisement2.out。

题目描述

JOI 国有 $N$ 名居民，编号为 1 到 $N$。居民 $i$（$1 \le i \le N$）住在数轴上的坐标 $X_i$ 处，其影响力为 $E_i$。同一坐标上也可能住着多名居民。影响力越高的居民宣传效果越大，但买书时也越谨慎。

理惠女士出版了一本信息科学方面的书。为了让更多的人买书，她可以向若干名居民赠书。若向居民 $i$（$1 \le i \le N$）赠书，则居民 $i$ 得到理惠女士的书。此外，在还没有理惠女士的书的居民中，满足以下条件的所有居民 $j$（$1 \le j \le N$）会买下理惠女士的书。

居民 $i$ 与居民 $j$ 在数轴上的距离不超过 $E_i - E_j$。即 $|X_i - X_j| \le E_i - E_j$。

如果理惠女士的书被 JOI 国的所有居民读到，信息学奥赛的知名度将会大幅提升。请编写程序求出为了让 JOI 国的全体居民都拿到理惠女士的书，最少需要向多少人赠书。

输入格式

输入以如下格式从文件 advertisement2.in 给出：

N
X_1 E_1
X_2 E_2
...
X_N E_N

输出格式

输出到文件 advertisement2.out 用 1 行输出理惠女士应当赠书的居民人数的最小值。

样例

样例 1

输入：

4
4 2
2 3
3 4
6 5

输出：

2

例如按如下方式赠书，JOI 国的全体居民就都能拿到理惠女士的书。

• 向居民 3 赠书。
• $|X_3 - X_1| = 1$，$E_3 - E_1 = 2$，因此居民 1 会买下理惠女士的书从而得到书。
• $|X_3 - X_2| = 1$，$E_3 - E_2 = 1$，因此居民 2 会买下理惠女士的书从而得到书。
• $|X_3 - X_4| = 3$，$E_3 - E_4 = -1$，因此居民 4 不会买理惠女士的书。

于是，居民 1, 2, 3 会得到理惠女士的书。

• 向居民 4 赠书。除居民 4 以外的居民都已经得到了理惠女士的书，因此 JOI 国的全体居民都得到了理惠女士的书。

少于 2 人的赠书无法让 JOI 国的全体居民都得到理惠女士的书，因此输出 2。

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

样例 2

输入：

3
7 10
10 10
7 10

输出：

2

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

样例 3

输入：

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

输出：

5

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

约束

• $1 \le N \le 500\,000$
• $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 1000$。
4. (31 点) 没有额外的约束。