#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n,m,wi[105];
char p[105][105],afp[105][105];
int o=0,tot;
int sum,lin[1005];
int d[maxn];
int vis[maxn];
int vii;

struct add {
	int to,w,nxt;
} e[2*maxn];
void adde(int x,int y,int w) {
	tot++;
	e[tot].to=y;
	e[tot].w=w;
	e[tot].nxt=lin[x];
	lin[x]=tot;
}
void dfs(int step,int s,int d) {
	
	if(step==n) {

		if(afp[d][step]=='+') sum=s|=(1<<d);
		if(afp[d][step]=='-') sum=s&=(1<<d);
		else {
			sum=s;
		}
		adde(s,sum,wi[d]);

		return ;
	}
	if(p[d][step]=='+') {
		dfs(step+1,2*s+1,d);
	} else if(p[d][step]=='-') {
		dfs(step+1,2*s,d);
	} else {
		dfs(step+1,2*s,d);
		dfs(step+1,2*s+1,d);
	}
}
void dijie(int ss)
{
	memset(d,0X3f3f3f3f,sizeof(d));
	d[ss]=0;
	for(int k=1;k<n;k++)
	{
		int q=n+1;
		for(int i=1;i<=n;i++)
		{
			if(vis[i]==0&&d[q]>d[i])
			{
				q=i;
			}
		}
		vis[q]=1;
		for(int j=lin[q];j;j=e[j].nxt)
		{
			vii=e[j].to;
			if(vis[j]==0&&d[vii]+e[j].w<d[vii])
			{
				d[vii]=d[vii]+e[j].w;
			}
		}
		
	}
	}

int main() {
	scanf("%d %d",&n,&m);
	for(int i=1; i<=m; i++) {

		cin>>wi[i]>>p[i]>>afp[i];

	}
	for(int j=1; j<=m; j++) {

		dfs(0,0,j);
		


	}
	dijie(1);
	int ww=2;
	for(int i=1;i<=n;i++)
	{
		ww*=2;
	}
	ww-=1;
	printf("%d",d[ww]);
	

	return 0;
}



/*
3[3个错误]   3[3个补丁]

1       000          00-
1       00-          0-+
2       0--          -++
边权    补丁前置     用了补丁后的状态
wi
*/