配点: 100 点
問題文
在JOI国家 有 N 居民, 它们的编号最大为1 减去 N 。 居民 i (1 \leqq i \leqq N) 是数轴上的坐标 我住在 X_i 并且影響力是 您也可以写 E_i 。多个居民可能居住在同一坐标。 居民影响力越大,广告效果越大,但购买图书时也越谨慎。
Rie出版了一本关于信息科学的书。为了让更多人购买您的书,您可以将其捐赠给多名居民。 居民 i (1 \leqq i \leqq N),居民 i 得到 Rie 的书。 另外,尚未拥有理惠之书的居民中,凡符合以下条件的居民 j (1 \leqq j \leqq N)买了Rie的书并得到了它。
- 住人 i 和居民 数轴上距 j 的距离为 E_i - E_j 下面。即 |X_i - X_j| \leqq E_i - E_j 是。
如果JOI国家的所有居民都阅读Rie的书,信息奥运会的受欢迎程度将会大大提高。 JOI 编写一个程序,找出需要捐赠 Rie 的书的最低人数,以便该国所有居民都能获得 Rie 的书。
入力
输入是按以下格式从标准输入给出的。
N X_1 E_1 X_2 E_2 \vdots X_N E_N
出力
Rie 应该向标准产出捐赠图书的最低居民数量。 1 行输出。
制約
- 1 \leqq N \leqq 500\,000.
- 1 \leqq X_i \leqq 10^9 (1 \leqq i \leqq N).
- 1 \leqq E_i \leqq 10^9 (1 \leqq i \leqq N).
- 所有输入值都是整数。
小課題
- (10 点) E_1 = E_2 = \cdots = E_N.
- (23 点) N \leqq 16.
- (36 点) N \leqq 1\,000.
- (31 点)没有额外的限制。
入力例 1
4 4 2 2 3 3 4 6 5
出力例 1
2
例如,如果您按照如下方式捐赠一本书,则JOI国家的所有居民都将能够获得理惠的书。 谨将此书献给
-
住人 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的书。 将本书献给
-
住人 4 。居民 除了 4 之外的所有居民都已经获得了理惠的书,所以现在JOI国的所有居民都获得了理惠的书。
2 JOI国的所有居民不可能通过向更少的人捐赠书籍来获得Rie的书籍。2 。
你只需要砍掉
此输入示例是一个小作业。 2, 3, 4 满足约束。
入力例 2
3 7 10 10 10 7 10
出力例 2
2
此输入/输出示例满足所有子任务约束。
入力例 3
10 31447678 204745778 430226982 292647686 327782937 367372305 843320852 822224390 687565054 738216211 970840050 766211141 563662348 742939240 103739645 854320982 294864525 601612333 375952316 469655019
出力例 3
5
此输入示例是一个小作业。 2, 3, 4 满足约束。