记录编号	332920	评测结果	AAAAAAAA
题目名称	王伯买鱼	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2016-10-29 14:25:36	内存使用	0.34 MiB

/*
	Name: 王伯买鱼 
	Copyright: 
	From：cogs 
	Author: Go灬Fire 
	Date: 29/10/16 14:26
	Description:当初考试完挂，现在虐它如虐傻瓜 
*/
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int maxn=1010;
struct Edge{
	int next,to,from;
}e[maxn];
int len,head[maxn],tot,n,v[maxn],ansnum,anstot;
bool us[maxn],ans[maxn];
int vis[maxn];
void Insert(int x,int y){
	len++;e[len].to=y;e[len].next=head[x];e[len].from=x;head[x]=len;
}
void Init();
void Dfs(int x,int num,int cost){
	if(cost>tot || n-x+1+num<ansnum)return;//小小的剪枝优化 
	if(x==n+1){
		if(num>ansnum){
			ansnum=num;anstot=cost;
			for(int j=1;j<=n;j++)ans[j]=us[j];
		}
		else if(num==ansnum && cost>anstot){
			anstot=cost;
			for(int j=1;j<=n;j++)ans[j]=us[j];
		}
		else if(num==ansnum && cost==anstot)for(int j=1;j<=n;j++)ans[j]=us[j];//如果有评测插件此句不需要 
		return;
	}
	if(vis[x])Dfs(x+1,num,cost);
	else {
		Dfs(x+1,num,cost);
		vis[x]++;us[x]=1;
		for(int i=head[x];i;i=e[i].next){
			int j=e[i].to;
			vis[j]++;
		}
		Dfs(x+1,num+1,cost+v[x]);
		vis[x]--;us[x]=0;
		for(int i=head[x];i;i=e[i].next){
			int j=e[i].to;vis[j]--;
		}
	}
}
int main(){
	freopen("fish.in","r",stdin);freopen("fish.out","w",stdout); 
    Init();
    //for(;;);
    getchar();getchar();
    return 0;
}
void Init(){
	scanf("%d%d",&tot,&n);
	for(int i=1;i<=n;i++){
		int x,y;scanf("%d%d",&x,&y);
		v[x]=y;
	}
	int x,y;
	while(scanf("%d%d",&x,&y) && x!=0 && y!=0)Insert(x,y),Insert(y,x);
	Dfs(1,0,0);
	printf("%d %d\n",ansnum,anstot);
	for(int i=1;i<=n;i++)if(ans[i])printf("%d\n",i);
}