题目名称	435. 王伯买鱼
输入输出	`fish.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	8
题目来源	cqw 于2010-04-21加入
开放分组	全部用户
提交状态
分类标签	搜索法剪枝动态规划
	分享题解

通过：133，提交：392，通过率：33.93%
_stranger	100	0.009 s	0.31 MiB	C++
哒哒哒哒哒！	100	0.010 s	0.31 MiB	C++
可以的.	100	0.011 s	0.29 MiB	C++
可以的.	100	0.011 s	0.29 MiB	C++
千世断魂自凝眉	100	0.011 s	0.29 MiB	C++
‎MistyEye	100	0.011 s	0.31 MiB	C++
_Itachi	100	0.019 s	0.29 MiB	C++
Hzoi_Go灬Fire	100	0.019 s	0.34 MiB	C++
Go灬Fire	100	0.021 s	0.34 MiB	C++
可以的.	100	0.022 s	0.25 MiB	C++

本题关联比赛
20100421

关于王伯买鱼的近10条评论(全部评论)
每次感觉十分正确的剪枝交上去就W，这蜜汁剪枝，醉了...... +1-1这玩意儿死算不对，我没救了= = AntiLeaf 2016-11-12 17:45 12楼
没有评测插件却让随便输出，有才有才 Hzoi_Go灬Fire 2016-10-29 14:23 11楼
额额额，考试时在分不清编号和种类的情况下，交上去了一个按种类字典序的代码。。。 _Itachi 2016-08-04 18:45 10楼
同上这题没有测评插件，得按字典序 521 2016-07-06 21:09 9楼
如果输出任意解，那么第6个数据有点问题 dateri 2016-06-05 09:36 8楼
回复 @乙阙溟河 : 你蠢喵了个咪的 2016-05-26 18:49 7楼
回复 @乙阙溟河 : HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH你是世间最后一个JI，理应我买你并吃了你喵了个咪的 2016-05-26 18:48 6楼
@喵了个咪的我可以买了你括弧笑 ————来自风流倜傥的小乙桑乙阙溟河 2016-05-26 18:47 5楼
王婆不卖瓜了，，卖瓜的钱都用来给王伯买鱼惹QWQ 喵了个咪的 2016-05-26 18:42 4楼
剪枝什么东西最不熟练 NVIDIA 2015-07-29 14:56 3楼

435. 王伯买鱼

★☆ 输入文件：fish.in 输出文件：fish.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

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

王伯想买尽可能多的鱼，但很可惜，他的资金有限。他冥思苦想，不知如何是好。请编写一个程序帮助他。如果有多个方案都能买尽可能多的鱼，选择所花资金最多的一个。

【输入】

从输入文件读入数据。输入文件的第一行为两个正整数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