← 返回题目列表

AtCoder · joi2023ho_b

B. 广告2

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

配点: 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).
  • 所有输入值都是整数。

小課題

  1. (10 点) E_1 = E_2 = \cdots = E_N.
  2. (23 点) N \leqq 16.
  3. (36 点) N \leqq 1\,000.
  4. (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 满足约束。