#include <cstdio>
using namespace std;

const int MAXN=31;

int n,m,p[MAXN],way[MAXN],ans[2],sum[MAXN];
bool e[MAXN][MAXN],used[MAXN],re[MAXN];

void search(int dep,int t,int money)
{
	if (money>m)return;
	if (n-dep+1+t<ans[0])return;
	if (dep==n+1&&t>=ans[0])
	{
		if (t==ans[0]&&money>ans[1])return;
		ans[0]=t;ans[1]=money;
		for(int i=1;i<=n;i++)
			re[i]=used[i];
		return;
	}
	int i;
	for(i=1;i<=n;i++)
		if (e[dep][i]&&used[i])
			break;
	if (i==n+1)
	{
	way[++way[0]]=dep;
	used[dep]=true;
	search(dep+1,t+1,money+p[dep]);
	way[0]--;	
	}
	used[dep]=false;
	search(dep+1,t,money);
}

int main()
{
	freopen("fish.in","r",stdin);
	freopen("fish.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=0;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		p[a]=b;
	}
	while(true)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		if (a==0&&b==0)break;
		e[a][b]=e[b][a]=true;
	}
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+p[i];
	search(1,0,0);
	printf("%d %d\n",ans[0],ans[1]);
	for(int i=1;i<=n;i++)
		if (re[i])
			printf("%d\n",i);
}