← 返回题目列表

Codeforces · 306/B

B. 优化器

中文机器翻译题面 查看原题

进程 RAM 是索引从 1 到 n 的字节序列。 Polycarpus的程序包含诸如“memset”之类的指令,即用某个值填充段上的存储单元的操作。详细信息是:代码仅包含m条看起来像“set13 a_i l_i”的指令。指令 i 填充长度为 li 的连续内存段,从单元编号 ai 开始(单元格编号为 ai、ai + 1、...、ai + li - 1),值为 13。

在 Polycarpus 的代码中,优化器的任务是从代码中删除最大数量的指令,以便剩余指令在优化前从代码中获取该值的所有内存字节中设置值 13。此外,值 13 应该仅设置在优化前从代码中获取该值的内存字节中。您的任务是为此类程序实现优化器。

输入

第一行包含整数 n 和 m (1 ≤ n ≤ 2·106, 1 ≤ m ≤ 2·105) — Polycarpus 代码中的字节数(存储单元)和指令数。接下来是 m 行,每行包含一对整数 ai,li (1 ≤ ai ≤ n, 1 ≤ li ≤ n - ai + 1)。

输出

在第一行打印所寻求的可以从代码中删除的最大指令数。在第二行中打印指令的编号。指令按照它们在输入中出现的顺序从 1 到 m 进行编号。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

10 4
3 3
3 1
4 1
9 2

输出 #1

2
2 3

输入 #2

1 1
1 1

输出 #2

0