C++ :

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 105;
int f[1048577], q[10000000], w, pay[MAXN];
int n, m, i, j, k, x, y, z, a[1048577], b[1048577], c[1048577], d[1048577];
bool e[1048577];
char cc[25];
int main()
{
	cin >> n >> m;
	for(j = 1; j <= m; j ++)
	{
		scanf("%d", &pay[j]);
		scanf("%s", cc + 1);
		for(i = 1; i <= n; i ++)
		{
			if (cc[i] == '+') a[j] |= (1 << n - i);
			if (cc[i] == '-') b[j] |= (1 << n - i);
		}
		scanf("%s", cc + 1);
		c[j] = (1 << n) - 1;
		for(i = 1; i <= n; i ++)
		{
			if (cc[i] == '-') c[j] ^= (1 << n - i);
			if (cc[i] == '+') d[j] |= (1 << n - i);
		}
	}
	int all = (1 << n) - 1;
	memset(f, 127 / 3, sizeof (f));
	f[all] = 0; e[all] = 1;
	q[w = 1] = all;
	for(int gzb = 1; gzb <= w; gzb ++)
	{
		k = q[gzb];
		for(i = 1; i <= m; i ++)
			if ((k & a[i]) == a[i] && !(k & b[i]))
			{
				int nex = k & c[i] | d[i];
				if (f[nex] > f[k] + pay[i])
				{
					f[nex] = f[k] + pay[i];
					if (!e[nex])
					{
						e[nex] = 1;
						q[++w] = nex;
					}
				}
			}
		e[k] = 0;
	}
	if (f[0] < 707406378) cout << f[0];
	else cout << 0;
}