开始: 2026-10-15 00:00:00

【集训10】模拟赛1015

结束: 2026-10-15 23:00:00
当前  2026-11-04 11:35:07  类型: IOI  状态: 已经结束 

P3. 打印店print
描述

开学季,学校打印店里排起了长队。店里只有一台打印机,每次只能打印一位顾客的文档,打印一份文档**恰好需要 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
提交