#include<cstdio>
#include<cstring>
using  namespace  std;
int  d[2100000],n,m,nn;
int  list[2100000],head=1,tail=2;
bool  v[2100000];
char  st[210];
struct  node
{
	int  x1,y1,x2,y2,o;
}tr[2100];
int  main()
{
	scanf("%d%d",&n,&m);
	int  p=n;
	while(p--)
	{
		nn=(nn<<1)+1;
	}
	list[head]=nn;
	for(int  i=1;i<=m;i++)
	{
		int  t1,t2;scanf("%d ",&t1);
		tr[i].o=t1;
		scanf("%s",st+1);
		t1=0;t2=0;
		for(int  j=1;j<=n;j++)
		{
			t1=t1<<1;t2=t2<<1;
			if(st[j]=='+')t1++;
			else  if(st[j]=='-')t2++;
		}
		tr[i].x1=t1;tr[i].y1=t2;
		scanf("%s",st+1);
		t1=0;t2=0;
		for(int  j=1;j<=n;j++)
		{
			t1=t1<<1;t2=t2<<1;
			if(st[j]=='-')t1++;
			else  if(st[j]=='+')t2++;
		}
		tr[i].x2=t1;tr[i].y2=t2;
	}
	memset(d,1,sizeof(d));d[nn]=0;
	memset(v,true,sizeof(v));v[nn]=false;
	int  inf=d[0];
	while(head!=tail)
	{
		int  x=list[head];
		for(int  i=1;i<=m;i++)
		{
			if((x&tr[i].x1)!=tr[i].x1  ||  (x&tr[i].y1)!=0)continue;
			int  y=(x&~tr[i].x2)|tr[i].y2; 
			if(d[y]>d[x]+tr[i].o)
			{
				d[y]=d[x]+tr[i].o;
				if(v[y]==true)
				{
					v[y]=false;
					if(d[list[head+1]]>d[y])
					{
						int  all=head;
						head--;if(head==0)head=nn;
						list[head]=list[all];list[all]=y;
					}
					else
					{
						list[tail++]=y;if(tail==nn+1)tail=1;
					}
				}
			}
		}
		head++;if(head==nn+1)head=1;
		v[x]=true;
	}
	if(d[0]==inf)printf("0\n");
	else  printf("%d\n",d[0]);
	return  0;
}