#include <bits/stdc++.h>
using namespace std;
struct rmd
{
	int b1,b2,f1,f2,t;
}p[101];
int dis[1048575],vis[1048575];
inline char read()
{
	char ch;
	ch=getchar();
	while(!(ch=='0' || ch=='-' || ch=='+')) ch=getchar();
	return ch;
}
struct node
{
	int now,d;
	bool operator < (const node &x) const
	{
		return d > x.d;
	}
};
priority_queue <node> q;
int n,m;
void Dijkstra()
{
	for(int i=0;i<=(1<<n)-1;i++) dis[i]=0x7f7f7f7f;
//    memset(dis,0x7f, 4* (1<<n));
	node temp;
	temp.now=(1<<n)-1;
	temp.d=0;
	dis[temp.now]=0;
	q.push(temp);
	while(!q.empty())
	{
		node tp=q.top();
		q.pop();
		int u=tp.now;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=1;i<=m;i++)
			if(((u&p[i].b1)==p[i].b1) && ((u&p[i].b2)==0))
			{
				int y=((u|p[i].f1)|p[i].f2)^p[i].f1;
				
				if(dis[u]+p[i].t<dis[y])
				{
					dis[y]=dis[u]+p[i].t;
					//cout<<y<<' '<<dis[y]<<endl;
					if(!vis[y])
					{
						node pp;
						pp.d=dis[y],pp.now=y;
						q.push(pp);
					}	
				}
			}	
		vis[u]=0;
	}
}
int main()
{
	cin>>m>>n;
	char ch;
	for(int i=1;i<=m;i++)
	{
		cin>>p[i].t;
		p[i].b1=p[i].b2=p[i].f1=p[i].f2=0;
		for(int j=1;j<=n;j++)
		{
			ch=read();
			if(ch=='-')
				p[i].b2|=(1<<(j-1));
			else if(ch=='+')
				p[i].b1|=(1<<(j-1));
		}
		for(int j=1;j<=n;j++)
		{
			ch=read();
			if(ch=='-')
				p[i].f1|=(1<<(j-1));
			else if(ch=='+')
				p[i].f2|=(1<<(j-1));
		}		
	}
	Dijkstra();
	if(dis[0]>=0x7f7f7f7f) cout<<0;
	else cout<<dis[0];
}