#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1<<21,maxm = 103,Inf = 100000000;
int N,M;
int T[maxm];
struct Movetype
{
	int s[3];
}Move[maxm][2],Queue[maxn];
int head,tail,len;
int Dis[maxn]; bool Mark[maxn];


void prep()
{
	scanf("%d%d",&N,&M);
	for (int i=1; i<=M; i++)
	{
		scanf("%d ",&T[i]);
		for (int j=1; j<=N; j++)
		{
			char ch; int p;
			scanf("%c",&ch);
			if (ch=='0') p = 0;
			if (ch=='-') p = 1;
			if (ch=='+') p = 2;
			Move[i][0].s[p] = Move[i][0].s[p] | (1<<(j-1));
		}
		scanf(" ");
		for (int j=1; j<=N; j++)
		{
			char ch; int p;
			scanf("%c",&ch);
			if (ch=='0') p = 0;
			if (ch=='-') p = 1;
			if (ch=='+') p = 2;
			Move[i][1].s[p] = Move[i][1].s[p] | (1<<(j-1));
		}
		scanf("\n");
	}
}

bool CanMove(Movetype a,int j,Movetype &b)
{
	int t = a.s[1] & Move[j][0].s[1];
	if (t <Move[j][0].s[1]) return false;
	t = a.s[2] & Move[j][0].s[2];
	if (t < Move[j][0].s[2]) return false;
	
	b.s[1] = a.s[1] & Move[j][1].s[0];
	b.s[1] = b.s[1] | Move[j][1].s[1];
	b.s[2] = a.s[2] & Move[j][1].s[0];
	b.s[2] = b.s[2] | Move[j][1].s[2];
	
	return true;
}


void SPFA(int S)
{
	head = tail = len = 1;
	Queue[1].s[1] = 0; Queue[1].s[2] = S;
	Mark[S] = true;
	for (int i=0; i<S; i++) Dis[i] = Inf; Dis[S] = 0;
	do
	{
		Movetype u = Queue[head];
		int s = u.s[2];
		Movetype v;
		for (int i=1; i<=M; i++)
			if (CanMove(u,i,v))
			{
				int ns = v.s[2];
				if (Dis[s] + T[i] <Dis[ns])
				{
					Dis[ns] = Dis[s] + T[i];
					if (!Mark[ns])
					{
						tail = tail%maxn+1; len++;
						Queue[tail] = v;
						Mark[ns] = true;
					}
				}
			}
		head = head%maxn + 1; len--; Mark[s] = false;
	}
	while (len);
}

void work()
{
	SPFA((1<<N)-1);
	if (Dis[0]!=Inf)
		printf("%d\n",Dis[0]);
	else
		printf("-1\n");
}

int main()
{
	freopen("bugs.in","r",stdin);
	freopen("bugs.out","w",stdout);
	prep();
	work();
	return 0;
}