开学季,学校打印店里排起了长队。店里只有一台打印机,每次只能打印一位顾客的文档,打印一份文档**恰好需要 1 单位时间**。
第 i 位顾客在**时刻 T_i** 到店,并把文档交给店员。这位顾客的耐心有限:他只愿意等到**时刻 T_i + D_i**。如果到那个时刻还没轮到他开始打印,他就直接走人(若恰好在时刻 T_i + D_i 开始打印,他仍愿意)。
打印机可以闲下来等顾客。请你帮店员规划打印顺序,求出**最多**能服务多少位顾客。
第一行一个整数 N;
接下来 N 行,每行两个整数 T_i, D_i。
一行一个整数:最多能服务的顾客数。
2 0 1 1 1
2
3 0 0 0 1 1 1
3
3 0 0 0 0 2 5
2
| t1 | 20 | N \le 6,T_i \le 12,D_i \le 6 |
| t2 | 20 | N \le 50,T_i \le 500,D_i \le 100 |
| t3 | 20 | N \le 2000,T_i \le 10^6 |
| t4 | 20 | N \le 2 \times 10^5,T_i, D_i \le 10^9 |
| t5 | 20 | N \le 2 \times 10^5,T_i \le 10^9,D_i \le 5 |
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |