#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
const int N = 20;
const int M = 105;
int n, m;
int wei[M];
int f1[M], f2[M];
string opt[M];

bool check(int u, string s){
    int stp = 0;
    while(u){
        int x = u&1;
        u >>= 1;
        if( s[stp] == '0' ){
            ++stp;
            continue;
        }
        else if( s[stp] == '+' ){
            if( !x ) return 0;
        }else{
            if( x ) return 0;
        }
        ++stp;
    }
    return 1;
}

int dis[(1<<N)+5];

void Dijkstra( int s ){
    memset(dis,0x7f,sizeof(dis));
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > q;
    q.push(make_pair(0,s));
    dis[s] = 0;
    while( !q.empty() ){
        int u = q.top().second;
        q.pop();
        for(int i = 1; i <= m ; i++ ){
            if( !check( u ,opt[i] ) ) continue;
            int v = u&(~f1[i]);
            v |= f2[i];
            if( dis[v] > dis[u]+wei[i] ){
                dis[v] = dis[u]+wei[i];
                q.push(make_pair(dis[v],v));
            }
        }
    }
}

int main() {
    cin >> n >> m;
    string s1,s2;
    for(int i = 1 ; i <= m; i++){
        cin >> wei[i] >> s1 >> s2;
        //cout << s1 <<endl;
        opt[i] = s1;
        for(int j = 0; j < s2.size(); j++){
            if( s2[j] == '0' ) continue;
            else if( s2[j] == '-' ) f1[i] |= (1<<j);
            else f2[i] |= (1<<j);
        }
    }
    Dijkstra((1<<n)-1);
    if( dis[0] < 0x7f7f7f7f ) cout << dis[0] <<endl;
    else cout << 0 <<endl;
    return 0;
}