记录编号	17801	评测结果	AAAAAAAA
题目名称	王伯买鱼	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2010-08-31 21:50:39	内存使用	0.26 MiB

#include <cstdio>
using namespace std;

const int MAXN=35;

struct Node
{
	int v;
	Node *next;
	Node(int a,Node *b):v(a),next(b){}
};

Node *adj[MAXN];
int cost[MAXN];
int n,m;

void add(int a,int b)
{
	adj[a]=new Node(b,adj[a]);
	adj[b]=new Node(a,adj[b]);
}

bool get[MAXN];

int best,way[MAXN],expen,top;
void search(int dep,int money,int nowfish)
{
	if (n-dep+nowfish<best)return;
	if (dep==n)
	{
		if (nowfish>best||(nowfish==best&&money>expen))
		{
			expen=money;
			top=0;best=nowfish;
			for(int i=0;i<dep;i++)
				if (get[i])
					way[top++]=i;
		}
		return ;
	}
	if (m-money>=cost[dep])
	{
		Node *p;
		for(p=adj[dep];p;p=p->next)
			if (get[p->v])
				break;
		if (!p)
		{		
			get[dep]=true;
			search(dep+1,money+cost[dep],nowfish+1);
			get[dep]=false;
		}
	}
	search(dep+1,money,nowfish);
}

int main()
{
	freopen("fish.in","r",stdin);
	freopen("fish.out","w",stdout);
	scanf("%d%d",&m,&n);
//	printf("%d %d\n",m,n);
	for(int i=0,a,b;i<n;i++)
	{
		scanf("%d%d",&a,&b);
//		printf("%d %d\n",a,b);
		a--;
		cost[a]=b;
	}
	while(true)
	{
		int a,b;
		scanf("%d%d",&a,&b);
//		printf("%d %d\n",a,b);
		if (!a&&!b)break;
		a--,b--;
		add(a,b);
	}
	search(0,0,0);
	printf("%d %d\n",best,expen);
	for(int i=0;i<top;i++)
		printf("%d\n",way[i]+1);
	return 0;
}