← 返回题目列表

Codeforces · 607/A

A. 连锁反应

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

有 n 个信标位于数轴上的不同位置。第 i 个信标的位置为 ai,功率级别为 bi。当第 i 个信标被激活时,它会销毁其左侧(坐标递减方向)距离 bi(含)内的所有信标。然而,信标本身并没有被摧毁。埼玉将从右到左一次激活一个信标。如果信标被摧毁,它就无法被激活。

埼玉希望杰诺斯严格在所有现有信标的右侧添加一个信标,可以设置任何位置和任何功率级别,以便尽可能少地摧毁信标数量。请注意,杰诺斯放置的信标意味着它将是第一个被激活的信标。帮助杰诺斯找到可以摧毁的最少数量的信标。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 信标的初始数量。

接下来 n 行的第 i 行包含两个整数 ai 和 bi (0 ≤ ai ≤ 1 000 000, 1 ≤ bi ≤ 1 000 000) – 分别是第 i 个信标的位置和功率级别。没有两个信标具有相同的位置,因此如果 i ≠ j,则 ai ≠ aj。

输出

打印一个整数——如果仅添加一个信标,则可以销毁的信标的最小数量。

示例

输入 #1

4
1 9
3 1
6 1
7 4

输出 #1

1

输入 #2

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

输出 #2

3

注意

对于第一个示例案例,被摧毁的信标的最小数量为 1。实现此目的的一种方法是将信标放置在位置 9 处,功率级别为 2。

对于第二个示例案例,被摧毁的信标的最小数量为 3。实现此目的的一种方法是将信标放置在位置 1337 处,功率级别为 42。