有 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。