打印机

题目描述

有 $N$ 件产品,编号为 $1$ 到 $N$,在传送带上流动。 传送带上安装了 Keyence 打印机,产品 $i$ 从现在起 $T_i$ 微秒后进入打印机的可打印范围,$D_i$ 微秒后离开可打印范围。

Keyence 打印机可以瞬间在可打印范围内的 1 件产品上完成打印(特别是,在产品进入或离开可打印范围的瞬间也可以打印)。 但是,打印一次之后,需要 1 微秒的充电时间才能再次打印。

在最优地选择打印的产品和时机的情况下,打印机最多可以打印多少件产品?

输入格式

输入按以下格式从标准输入给出:

$N$
$T_1$ $D_1$
$T_2$ $D_2$
$\vdots$
$T_N$ $D_N$

输出格式

输出打印机最多可以打印的产品数量。

样例

5
1 1
1 1
2 1
1 2
1 4

4

下面,将从现在起 $t$ 微秒的时刻简称为时刻 $t$。

例如,可以按如下方式打印 4 件产品:

• 时刻 1:产品 1、2、4、5 进入可打印范围。打印产品 4。
• 时刻 2:产品 3 进入可打印范围,产品 1、2 离开可打印范围。打印产品 1。
• 时刻 3:产品 3、4 离开可打印范围。打印产品 3。
• 时刻 4.5:打印产品 5。
• 时刻 5:产品 5 离开可打印范围。

无法打印全部 5 件产品,所以答案是 4。

2
1 1
1000000000000000000 1000000000000000000

2

10
4 1
1 2
1 4
3 2
5 1
5 1
4 1
2 1
4 1
2 4

6

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le T_i, D_i \le 10^{18}$
• 所有输入值均为整数