问题2444--印刷机

2444: 印刷机

[命题人 : ]
时间限制 : 12 sec  内存限制 : 128 MB

提交

题目描述

有 $N$ 个标有 $1$ 至 $N$ 的产品在传送带上流动。传送带上有一台 晨光打印机,产品 $i$ 在 $T_i$ 微秒后进入打印机的打印范围,并在 $D_i$ 微秒后离开打印机(也就是说这个产品需要占用打印机$D_i$ 微秒)。

晨光打印机可以即时打印打印机范围内的一个产品(尤其是在产品进入或离开打印机范围的瞬间)。但打印一次后,需要充电 $1$ 微秒才能再次打印。如果产品和打印机打印时间选择最优,打印机最多可以打印多少产品?

输入

第一行一个整数N表示共有N个产品
接下来N行,每行两个整数分别表示产品 $i$ 在 $T_i$ 微秒后进入打印机的打印范围,并在 $D_i$ 微秒后离开打印机
  • $ 1\leq\ N\ \leq\ 2\times\ 10^5 $
  • $ 1\leq\ T_i,D_i\ \leq\ 10^{18} $
  • 所有输入值均为整数

输出

输出一个整数,表示打印机最多可以打印多少产品

样例输入 Copy

5
1 1
1 1
2 1
1 2
1 4

样例输出 Copy

4

提示

样例输入2:
10 
4 1
1 2
1 4
3 2
5 1
5 1
4 1
2 1
4 1
2 4
样例输出2:
6
样例输入3:
2
1 1
1000000000000000000 1000000000000000000
样例输出3:
2