273. [NOI 1998]软件安装盘

软件安装通常是一件令人头疼的事。软件一般都包括若干个相对独立的部分（称为“组件”），在安装的时候由用户决定安装哪些部分。并且，这些相对独立的组件之间在安装时有一定的先后顺序要求。

由于当代的个人计算机普遍安装了软盘驱动器，所以软件的最流行的载体形式是软盘。然而，由于软盘的容量有限，稍大一些的软件就无法用一张软盘装下。这时，这些软件往往要用很多张软盘来存储。每张磁盘上存储了软件的一个或多个组件。这些软盘称为软件的安装盘。

由于软件的各个组件分散在不同的软盘上，而在安装时又有一定的先后顺序要求，所以很容易发生要求用户反复换盘的情况。而计算机用户在安装软 件的时候，最反感的就是反复在软盘之间切换：找盘、插盘、取盘、找盘、插盘、取盘、…，一切都显得那么琐碎和无序。因此，有必要对软件安装盘的制作提出下 述要求：

永远不要让用户将一张磁盘插入两次。更精确地，要求对安装盘从1开始顺序编号，使得安装的时候，用户只要按顺序插入磁盘即可。

出于经济的考虑，通常要求安装盘的总数最少。写一个程序，对于给定的软件，制定最优的安装盘方案。

输入

• 输入文件的第一行是一个正整数M（1<= M<= 109），给出了每张磁盘的最大容量（字节数）。
• 输入文件的第二行是一个正整数N（1<= N<= 100），给出了软件的组件数。接下来的N行每行给出一个组件的详细信息。包括：

1. 组件所占的字节数；
2. 在安装该组件之前应先安装的组件序号（如有多个组件须先安装，则每个都应列出其序号，若无须先安装其它组件，则该行只含组件所占字节数）。

• 输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出

输出文件的第一行给出了最优安装盘方案的软盘数。如果不存在最优安装盘方案，则输出0。接下来的每一行顺序给出了每张盘上存储的组件的序号。如果一张盘上存储了多个组件，则输出所有这些组件的序号，中间用一个空格隔开。

样例输入

1457664
3
512665
912345 1
832542 1

样例输出

2
1 2
3