[NOI1998]软件安装盘

成绩 0 开启时间 2013年01月22日 星期二 14:00
折扣 0.8 折扣时间 2013年01月22日 星期二 14:00
允许迟交 关闭时间 2013年01月22日 星期二 14:00
输入文件 software.in 输出文件 software.out

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

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

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

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

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

输入

  • 输入文件的第一行是一个正整数M(1<= M<= 109),给出了每张磁盘的最大容量(字节数)。
  • 输入文件的第二行是一个正整数N(1<= N<= 100),给出了软件的组件数。接下来的N行每行给出一个组件的详细信息。包括:
  1. 组件所占的字节数;
  2. 在安装该组件之前应先安装的组件序号(如有多个组件须先安装,则每个都应列出其序号,若无须先安装其它组件,则该行只含组件所占字节数)。
  • 输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出

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

样例输入

1457664
3
512665
912345 1
832542 1

样例输出

2
1 2
3