题目描述
有 N 个人,人 i 在位置 Xi,具有影响力 Ei。
如果 i 知道了一件事情,则所有满足 ∣Xi−Xj∣≤Ei−Ej 的 j,都会知道这件事情。
你想让所有人都知道某件事情,请你求出在一开始,至少需要告诉多少人。
输入格式
第一行一个正整数 N。
接下来 N 行,第 i 行有两个整数 Xi,Ei。
输出格式
输出一行一个整数表示答案。
样例
样例输入
4
4 2
2 3
3 4
6 5
样例输出
2
样例解释
告诉 3,4 即可。
数据范围与约定
对于所有数据,有:
- 1≤N≤5×105
- 1≤Xi,Ei≤109
| 子任务编号 |
特殊性质 |
分值 |
| 1 |
E1=E2=⋯=EN |
25 |
| 2 |
N≤16 |
| 3 |
N≤103 |
| 4 |
无 |