王伯买鱼

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 fish.in 输出文件 fish.out
【问题描述】

王伯退休后开始养鱼。他一早起来就赶去动物公园，发现这个世界的鱼真不少，五光十色、色彩斑斓，大的、小的，什么都有。这些鱼实在是太美了，买的人越来越多，湖里的鱼越来越少。没有美丽的鱼，哪里有美丽的湖?于是动物公园不得不规定，对于每种鱼，每个人最多只能买一条。并且有些鱼是不能一起买的，因为它们之间会互相争斗吞食。

王伯想买尽可能多的鱼，但很可惜，他的资金有限。他冥思苦想，不知如何是好。请编写一个程序帮助他。如果有多个方案都能买尽可能多的鱼，选择所花资金最多的一个。
 
【输入】
从输入文件读入数据。输入文件的第一行为两个正整数M(M≤1000)，N(N≤30)，分别表示王伯的资金和鱼的种类。以下N行，每行有两个正整数S(1≤S≤N)，T，分别表示某种鱼的编号以及该鱼的价格。
接着，每行有两个整数P，Q。当P，Q均大于0时，表示P，Q不能共处；当P，Q均等于0时，表示输入文件的结束。
 
【输出】
输出文件的第一行为两个正整数X，y，分别表示所买鱼的条数和总花费。以下X行，每行有一个正整数，表示所买鱼的编号。编号按升序排列输出。
如果题目有多个解，只需输出其中的一个。
 
【输入输出样例】
样例输入（fish.in）:
170 7
 1 70
 2 50
 3 30
 4 40
 5 40
 6 30
 7 20
 1 4
 1 7
 3 4
 3 5
 5 7
 6 7
 0 0
样例输出（fish.out）：
4 160
2
4
5
6