P12916 [POI 2021/2022 R1] 剪辑师 / Montażysta

翻译来自于 [LibreOJ](https://loj.ac/p/4103)。

**题目译自 [XXIX Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Montażysta](https://sio2.mimuw.edu.pl/c/oi29-1/p/mon/)** 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$，你的程序可以输出任意一种。

**附加样例** 1. 该样例满足 $n=1000 ; t_{i}=5 \cdot 10^{8}, d_{i}=i \cdot 10^{6}$。答案是 $2$。 2. 该样例满足 $n=1000 , t_{i}=2, d_{i}=1999$。答案是 $999$。 3. 该样例满足 $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$ |