连锁反应 - 代码源竞赛平台

题目描述

数轴上有 $n$ 个位置各不相同的信标。第 $i$ 个信标位于 $a_i$，爆炸半径为 $b_i$。它被激活时，会摧毁左侧距离不超过 $b_i$ 的所有信标（包括距离恰好为 $b_i$ 的信标），但不会摧毁自己。

蜗蜗按位置从右到左依次激活信标。若某个信标已被摧毁，它就不能再激活。现在，朋友要在所有原有信标的右侧恰好新增一个信标，新信标的位置和爆炸半径都可以自行选择，并且它会最先激活。

求整个过程中，原有的 $n$ 个信标最少有多少个被摧毁。

输入格式

第一行包含一个整数 $n$，表示原有信标数。

接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，表示一个信标的位置和爆炸半径。输入顺序不保证与位置顺序相同。

输出格式

输出一行一个整数，表示原有信标中最少被摧毁的数量。

样例

3
1 1
3 2
5 2

1

2
0 1
100 1000000

1

样例解释

样例 1 中，把新信标放得足够远，使它不摧毁原有信标。随后位置 $5$ 的信标摧毁位置 $3$ 的信标，位置 $1$ 的信标仍能保留，因此只摧毁 $1$ 个。

样例 2 中，位置 $100$ 的信标会摧毁位置 $0$ 的信标，至少有 $1$ 个原有信标被摧毁。

数据范围

对于 100% 的数据，保证 $1\le n\le 10^5$，$0\le a_i\le 10^6$，$1\le b_i\le 10^6$，且任意两个原有信标的位置不同。