You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在数轴上有 $n$ 个信标，每个信标的位置互不相同。第 $i$ 个信标位于 $a_i$ 位置，具备能量 $b_i$。当第 $i$ 个信标被激活时，它会摧毁所有在其左侧（坐标更小的方向）距离 $b_i$（含边界）内的信标，但不会摧毁自己。Saitama 将会从右到左依次激活这些信标。如果某个信标已经被摧毁，则不会被激活。

Saitama 希望 Genos 在所有信标的严格右侧增加一个新的信标，位置和能量均可任意选择，使得被摧毁的信标数最少。注意，Genos 增加的新信标将会是第一个被激活的信标。请帮助 Genos 求出在只增加一个信标的情况下，最少能被摧毁的信标数量。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 100000$），表示初始信标数量。

接下来的 $n$ 行每行包含两个整数 $a_i$ 和 $b_i$（$0 \leq a_i \leq 1000000$，$1 \leq b_i \leq 1000000$），分别表示第 $i$ 个信标的位置和能量。不会有两个信标处于同一位置，即 $a_i \ne a_j$ 当 $i \ne j$ 时。

输出格式

输出一个整数，表示在恰好添加一个信标的情况下，最少能被摧毁的信标数量。

4
1 9
3 1
6 1
7 4

1

7
1 1
2 1
3 1
4 1
5 1
6 1
7 1

3

说明/提示

对于第一个样例，最少只能摧毁 $1$ 个信标。一种实现方式是在位置 $9$ 处放置能量为 $2$ 的信标。

对于第二个样例，最少会有 $3$ 个信标被摧毁。一种实现方式是在位置 $1337$ 处放置能量为 $42$ 的信标。