题目描述

题目译自 XXIX Olimpiada Informatyczna – I etap Montażysta

Bajtazar 接手了剪辑 $n$ 部关于 POI 题目讲解的视频的任务。已知剪辑第 $i$ 部视频需要 $t_{i}$ 天，并且必须在第 $d_{i}$ 天之前发布。Bajtazar 有光纤网络，所以剪辑好的视频可以立即上传到服务器上。但是剪辑过程非常耗费硬件资源，而 Bajtazar 只有一台电脑，所以他一次只能剪辑一部视频。

视频很多，Bajtazar 担心他不能按时完成所有的任务。请你帮助他，计算出如果他最早可以在第 $1$ 天开始剪辑，他最多能按时发布多少部视频。为了让 Bajtazar 更有信心，你还需要给出一个具体的工作计划，说明如何达到这个结果。

输入格式

输入的第一行包含一个整数 $n\ (1 \leq n \leq 5\cdot 10^5)$，表示要剪辑的视频的数量。

接下来的 $n$ 行，每行包含两个整数 $t_{i}, d_{i}\ (1 \leq t_{i}, d_{i} \leq 10^{9})$，表示第 $i$ 部视频的剪辑时间和发布期限。

输出格式

第一行输出一个整数 $m$，表示 Bajtazar 最多能按时发布的视频的数量。

接下来的 $m$ 行，你需要给出一个工作计划；第 $i$ 行应该包含两个整数 $f_{i},k_{i}\ (1 \leq f_{i} \leq n, 1 \leq k_{i})$，表示第 $f_{i}$ 号视频应该在第 $k_{i}$ 天开始剪辑。如果有多种方案可以达到最大的 $m$，你的程序可以输出任意一种。

5
4 5
2 4
5 3
1 9
3 10

3
2 3
4 7
5 8

样例 2

见附加文件下 [mon1.in](file:mon1.in) 和 [mon1.out](file:mon1.out)。

该样例满足 $n=1000 ; t_{i}=5 \cdot 10^{8}, d_{i}=i \cdot 10^{6}$。答案是 $2$。

样例 3

见附加文件下 [mon2.in](file:mon2.in) 和 [mon2.out](file:mon2.out)。

该样例满足 $n=1000 , t_{i}=2, d_{i}=1999$。答案是 $999$。

样例 4

见附加文件下 [mon3.in](file:mon3.in) 和 [mon3.out](file:mon3.out)。

该样例满足 $n=5\cdot 10^5, t_{i} \in\{1,2,3\}, d_{i}=10^{9}$。答案是 $5\cdot 10^5$。

数据范围与提示

详细子任务附加限制及分值如下表所示。如果你的程序正确地输出了 $m$，而方案不正确，你将获得该测试点 $50 \%$ 的分数。

子任务编号	附加限制	分值
$1$	$n \leq 10$	$20$
$2$	$n \leq 1000$	$30$
$3$	$t_{i}, d_{i} \leq 10^{6}$	$20$
$4$	无附加限制	$30$