#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;
const int oo=2000000000;
int limit,n,v[50];

struct fish
{
	int v,id;
}P[50];

bool operator <(fish a,fish b){return a.v-b.v;}

struct edge
{
	int t;
	edge *next;
}E[5000],*V[50];
int eh;
inline void addedge(int a,int b)
{
	E[++eh].next=V[a]; V[a]=E+eh; V[a]->t = b;
	E[++eh].next=V[b]; V[b]=E+eh; V[b]->t = a;
}

void init()
{
	scanf("%d%d",&limit,&n);
	for (int i=1;i<=n;i++)
		scanf("%d%d",&P[i].id,&P[i].v);
	sort(P+1,P+n);
	int a,b;
	do
	{
		scanf("%d%d",&a,&b);
		if (a!=0 && b!=0) addedge(a,b);
	}while (a!=0 && b!=0);
}
int num[50],cost,ge,anscost,ansge,i;
bool y[50],ansy[50];
void dfs(int u)
{
	i++;
	if (u>n)
	{
		if (cost<=limit)
		{
			if (ge>ansge)
			{
				ansge=ge;
				anscost=cost;
				memcpy(ansy,y,sizeof(y));
			}
			else if (ge==ansge && anscost>cost)
			{
				anscost=cost;
				memcpy(ansy,y,sizeof(y));
			}
		}
	}
	else 
	{	
		if (!num[P[u].id])
		{
			cost+=P[u].v;
			ge++;y[P[u].id]=true;
			for (edge *e=V[P[u].id];e;e=e->next)
			num[e->t]++;
			
			if (i<=10000000) dfs(u+1);
			
			for (edge *e=V[P[u].id];e;e=e->next)
			num[e->t]--;
			cost-=P[u].v;
			ge--;y[P[u].id]=false;
		}
		if (i<=10000000) dfs(u+1);
	}
	
}

int main()
{
	freopen("fish.in","r",stdin);
	freopen("fish.out","w",stdout);
	init();
	anscost=oo;
	ansge=0;
	dfs(1);
	printf("%d %d\n",ansge,anscost);
	for (int i=1;i<=n;i++)
	{
		if (ansy[i]) printf("%d\n",i);
	}
	return 0;
}