#include<bits/stdc++.h>
using namespace std;
int n,m,cost[101],b1[101],b2[101],f1[101],f2[101],len,dis[1145141];
bool vis[1145141];
string p,q;
struct node {
	int siz,num;
	bool operator <(const node&x)const {
		return x.num<num;
	}
};
int main() {
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		cin>>cost[i]>>p>>q;
		for(int j=0; j<n; j++) {
			if(p[j]=='+')b1[i]=b1[i]+(1<<(n-j-1));
			else if(p[j]=='-')b2[i]=b2[i]+(1<<(n-j-1));
			if(q[j]=='-')f1[i]=f1[i]+(1<<(n-j-1));
			else if(q[j]=='+')f2[i]=f2[i]+(1<<(n-j-1));
		}
	}
	len=(1<<n)-1;
	memset(dis,0x3f3f3f3f,sizeof(dis));
	priority_queue<node>Q;
	Q.push((node) {
		len,0
	});
	dis[len]=0;
	while(!Q.empty()) {
		node a=Q.top();
		Q.pop();
		int x=a.siz,b=0;
		if(vis[x])continue;
		vis[x]=true;
		for(long long i=1; i<=m; ++i) {
			if((x&b1[i])==b1[i]&&!(x&b2[i])) {
				b=(((x|f1[i])^f1[i])|f2[i]);
				if(dis[b]>dis[x]+cost[i]) {
					dis[b]=dis[x]+cost[i];
					if(!vis[b]) {
						Q.push((node) {
							b,dis[b]
						});
					}
				}
			}
		}
	}
	if(dis[0]!=dis[1145141])cout<<dis[0]<<endl;
	else cout<<"0";
	return 0;
}