/*
可以这很强势
一遍写完调试了两分钟过了样例直接AC秒杀~
和P1026很像    都是可以位运算处理然后转换SPFA
当然bfs+hash也是可以的
题目的确有点繁琐(当初看到这个逃了好几次)
但是静下心来仔细看就好了
check函数和get函数很精妙
位运算又进一步加强了
这种题目还是要自己多写写好
详细看P1026的题解叭~~~
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN=(1<<16)-1;
const int MAXM=102;
const int INF=(1<<30)-1;
int B1[MAXM],B2[MAXM];
int F1[MAXM],F2[MAXM];
bool in[MAXN];
queue<int> q;
int t[MAXM];
int d[MAXN];
int n,m;
int s;

void init()
{
    string a,b;
    cin>>n>>m;
    s=(1<<n)-1;
    for(int i=1;i<=m;i++)
    {
        cin>>t[i]>>a>>b;
        for(int j=0;j<n;j++)
            if(a[j]=='+')
                B1[i]|=(1<<j);
            else    if(a[j]=='-')
                B2[i]|=(1<<j);
        for(int j=0;j<n;j++)
            if(b[j]=='-')
                F1[i]|=(1<<j);
            else    if(b[j]=='+')
                F2[i]|=(1<<j);
    }
    for(int i=0;i<MAXN;i++)
        d[i]=INF;
}

bool check(int x,int k)
{
    for(int i=0;i<n;i++)
        if((1<<i)&B1[k]&&(!((1<<i)&x)))
            return 0;
    for(int i=0;i<n;i++)
        if((1<<i)&B2[k]&&(1<<i)&x)
            return 0;
    return 1;
}

int get(int x,int k)
{
    x&=(~F1[k]);
    x|=F2[k];
    return x;
}

void SPFA()
{
    d[s]=0; q.push(s);  in[s]=1;
    while(!q.empty())
    {
        int u=q.front();    q.pop();
        in[u]=0;
        for(int i=1;i<=m;i++)
        {
            if(!check(u,i))
                continue;
            int v=get(u,i);
            if(d[v]>d[u]+t[i])
            {
                d[v]=d[u]+t[i];
                if(!in[v])
                {
                    q.push(v);
                    in[v]=1;
                }
            }
        }
    }
    if(d[0]==INF)
        cout<<0<<endl;
    else
        cout<<d[0]<<endl;
}

int main()
{
    init();
    SPFA();
    return 0;
}
     

#include<iostream>
#include<math.h>
#include<string>
#include<memory.h>
using namespace std;
const int MAXN = 15;
const int MAXM = 101;
const int MAXV = 32768;
const int MAXT = 10000000;

typedef pair<int, int> P ;

struct Node {
    int time;
    P con[MAXN];
    int clen;
    P tra[MAXN];
    int tlen;
}nodes[MAXM];
bool vis[MAXV];
int n, m;
int tans = 0;
int ans = MAXT;

bool OK(int sta, Node node) {
    int k;
    for (int i = 0; i<node.clen; i++) {
        k = node.con[i].first;
        if ((1 & (sta >> k)) != node.con[i].second)
            return 0;
    }
    return 1;
}

int nextSta(int sta, Node node) {
    int k;
    for (int i = 0; i<node.tlen; i++) {
        k = node.tra[i].first;
        sta = sta - ((1 << k)&sta) + (node.tra[i].second << k);
    }
    return sta;
}

void dfs(int sta) {
    vis[sta] = 1;
    if (tans >= ans);
    else if (sta == 0) {
        if (tans<ans)
            ans = tans;
    }
    else {
        int nextsta;
        for (int i = 0; i<m; i++) {
            if (OK(sta, nodes[i])) {
                nextsta = nextSta(sta, nodes[i]);
                if (!vis[nextsta]) {
                    tans += nodes[i].time;
                    dfs(nextsta);
                    tans -= nodes[i].time;
                }
            }
        }
    }
    vis[sta] = 0;
}

int main() {
    cin >> n >> m;
    string str1, str2;
    int i, j;
    for (i = 0; i<m; i++) {
        cin >> nodes[i].time >> str1 >> str2;
        nodes[i].clen = 0;
        nodes[i].tlen = 0;
        for (j = 0; j<n; j++) {
            switch (str1[j]) {
            case '0':
                break;
            case '+':
                nodes[i].con[nodes[i].clen].first = j;
                nodes[i].con[nodes[i].clen].second = 1;
                nodes[i].clen++;
                break;
            case '-':
                nodes[i].con[nodes[i].clen].first = j;
                nodes[i].con[nodes[i].clen].second = 0;
                nodes[i].clen++;
                break;
            }
            switch (str2[j]) {
            case '0':
                break;
            case '+':
                nodes[i].tra[nodes[i].tlen].first = j;
                nodes[i].tra[nodes[i].tlen].second = 1;
                nodes[i].tlen++;
                break;
            case '-':
                nodes[i].tra[nodes[i].tlen].first = j;
                nodes[i].tra[nodes[i].tlen].second = 0;
                nodes[i].tlen++;
                break;
            }
        }
    }
    memset(vis, 0, sizeof(vis));
    dfs((1 << n) - 1);
    if (ans != MAXT)
        cout << ans << endl;
    else
        cout << 0 << endl;
    return 0;
}

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
int n,m,ans=0x7fffffff/2,Time[105],Use[105][25],Effect[105][25],Hash[70005];
bool Check(int state,int num) {
    for(int i=1; i<=n; i++) {
        if(!(state&(1<<(i-1)))&&Use[num][i]==1)return false;
        if((state&(1<<(i-1)))&&Use[num][i]==-1)return false;
    }
    return true;
}
void Dfs(int state,int ttime) {
    if(ttime>ans)return;
    if(Hash[state]<=ttime)return;
    Hash[state]=ttime;
    if(state==0) {
        ans=min(ans,ttime);
        return;
    }
    int nextstate;
    for(int i=1; i<=m; i++) {
        if(!Check(state,i))continue;
        nextstate=state;
        for(int j=1; j<=n; j++)
            if((state&(1<<(j-1)))&&Effect[i][j]==-1)nextstate^=1<<(j-1);
            else if(!(state&(1<<(j-1)))&&Effect[i][j]==1)nextstate^=1<<(j-1);
        Dfs(nextstate,ttime+Time[i]);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>Time[i];
        for(int j=1; j<=n; j++) {
            char x;
            cin>>x;
            if(x=='-')Use[i][j]=-1;
            if(x=='+')Use[i][j]=1;
        }
        for(int j=1; j<=n; j++) {
            char x;
            cin>>x;
            if(x=='-')Effect[i][j]=-1;
            if(x=='+')Effect[i][j]=1;
        }
    } 
    memset(Hash,0x3f,sizeof(Hash));
    Dfs((1<<n)-1,0);
    if(ans==0x7fffffff/2)puts("0");
    else printf("%d\n",ans);
    return 0;
}

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
struct Edge {
    int from,to,dist;
};
vector<Edge>edges[35005];
int dist[35005],inque[35005],n,m,Time[105],Use[105][25],Effect[105][25];
void AddEdge(int x,int y,int v) {
    edges[x].push_back((Edge) {
        x,y,v
    });
}
void Spfa(int s) {
    memset(dist,0x3f,sizeof(dist));
    queue<int>Q;
    Q.push(s);
    inque[s]=1;
    dist[s]=0;
    while(!Q.empty()) {
        int Now=Q.front();
        inque[Now]=0;
        Q.pop();
        for(int i=0; i<edges[Now].size(); i++) {
            Edge& e=edges[Now][i];
            int Next=e.to;
            if(dist[Now]+e.dist<dist[Next]) {
                dist[Next]=dist[Now]+e.dist;
                if(!inque[Next]) {
                    inque[Next]=1;
                    Q.push(Next);
                }
            }
        }
    }
}
bool Check(int state,int num) {
    for(int i=1; i<=n; i++) {
        if(!(state&(1<<(i-1)))&&Use[num][i]==1)return false;
        if((state&(1<<(i-1)))&&Use[num][i]==-1)return false;
    }
    return true;
}
int Get_Next(int state,int num) {
    int nextstate=state;
    for(int j=1; j<=n; j++)
        if((state&(1<<(j-1)))&&Effect[num][j]==-1)nextstate^=1<<(j-1);
        else if(!(state&(1<<(j-1)))&&Effect[num][j]==1)nextstate^=1<<(j-1);
    return nextstate;
} 
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>Time[i];
        for(int j=1; j<=n; j++) {
            char x;
            cin>>x;
            if(x=='-')Use[i][j]=-1;
            if(x=='+')Use[i][j]=1;
        }
        for(int j=1; j<=n; j++) {
            char x;
            cin>>x;
            if(x=='-')Effect[i][j]=-1;
            if(x=='+')Effect[i][j]=1;
        }
    } 
    for(int i=0; i<=(1<<n)-1; i++)
        for(int j=1; j<=m; j++)
            if(Check(i,j))AddEdge(i,Get_Next(i,j),Time[j]);
    Spfa((1<<n)-1);
    if(dist[0]==0x3f3f3f3f)puts("0");
    else printf("%d\n",dist[0]);
    return 0;
}

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
using namespace std;

const int INF = 1000000000;
const int maxn = 15;
const int maxm = 100 + 10;
int n, m;
int  d[1<<maxn];
bool done[1<<maxn];

struct Patch {
    string s1, s2;
    int cost;
    Patch(string s1, string s2, int cost) : s1(s1), s2(s2), cost(cost) {}
};

vector<Patch> patchs;

struct HeapNode {
    int u, d;
    HeapNode (int u, int d) : u(u), d(d) {}
    bool operator < (const HeapNode& rhs) const {
        return d > rhs.d;
    }
};

bool check (int x, const string& s) {
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '+' && !(x & (1<<i))) return false;
        if (s[i] == '-' && (x & (1<<i))) return false;
    }
    return true;
}

int add_patch (int x, const string& s) {
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '+') x |= (1<<i);
        if (s[i] == '-' && (x & (1<<i))) x ^= (1<<i);
    }
    return x;
}

void djs (void) {
    priority_queue<HeapNode> Q;
    Q.push(HeapNode((1<<n)-1, 0));
    d[(1<<n)-1] = 0;
    
    while (!Q.empty()) {
        HeapNode x = Q.top(); Q.pop();
        int u = x.u;
        if (done[u]) continue;
        done[u] = true;
        
        for (int i = 0; i < patchs.size(); i++) 
            if (check(u, patchs[i].s1)) { 
                int to = add_patch(u, patchs[i].s2);
                if (d[u] + patchs[i].cost < d[to]) {
                    d[to] = d[u] + patchs[i].cost;
                    Q.push(HeapNode(to, d[to]));
                }
            }
    }
}

int main ()
{
//  freopen ("in.txt", "r", stdin);
    cin >> n >> m;
    int c;
    string s1, s2;
    for (int i = 0; i < m; i++) {
        cin >> c >> s1 >> s2;
        patchs.push_back(Patch(s1, s2, c));
    }
    
    for (int i = 0; i < (1<<n); i++) d[i] = INF;
    djs();
    if (d[0] >= INF) cout << 0 << "\n";
    else cout << d[0] << "\n";
    
    return 0;
}

#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;

const int INF = 2147483647;

struct Po
{
    int th,dis;
    Po(int a,int b) : th(a) , dis(b) {};
    bool operator> (Po const &a) const{return dis > a.dis; }
};

struct Ed
{
    int span;
    vector<char> nodetail;
    vector<char> fudetail;
    Ed(int a) : span(a) {};
};

int n,m;
bool vis[32800];
vector<Ed> edges;
vector<Po> points;
priority_queue<Po,vector<Po>,greater<Po> > Q;

bool is_ok(int now,int th,int &next)
{
    Ed &ed=edges[th];
    for(int i=0;i<n;i++)
    {
        if(ed.nodetail[i]=='+'&& (  ( now&(1<<(n-1-i)) )!=(1<<(n-1-i)) ) ) return false;
        if(ed.nodetail[i]=='-'&&  ((now&(1<<(n-1-i)))!=0))                   return false;
    }
    next=now;
    for(int i=0;i<n;i++)
    {
        if(ed.fudetail[i]=='+')  next=next|(1<<(n-1-i));
        if(ed.fudetail[i]=='-' && ((now&(1<<(n-1-i)))==(1<<(n-1-i))))   next=next-(1<<(n-1-i));
    }
    return true;
}

void djs()
{
    memset(vis,0,sizeof(vis));
    int b=(1<<n) -1;
    points[b].dis=0;
    Q.push(points[b]);
    while(!Q.empty())
    {
        int k=(Q.top()).th; Q.pop();
        if(vis[k]) continue;
        Po &now=points[k];vis[k]=true;
        int next;
        if(vis[0]) break;
        
        for(int i=0;i<(int)edges.size();i++)
            if(is_ok(k,i,next)&&!vis[next]&&points[next].dis>now.dis+edges[i].span)
            {
                points[next].dis=now.dis+edges[i].span;
                Q.push(points[next]);
            }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int k; char st;
        scanf("%d",&k);
        edges.push_back(Ed(k));
        while((int)edges[edges.size()-1].nodetail.size()<n){
            scanf("%c",&st);
            if(st=='+'||st=='-'||st=='0')
            edges[edges.size()-1].nodetail.push_back(st);
            }
        while((int)edges[edges.size()-1].fudetail.size()<n){
            scanf("%c",&st);
            if(st=='+'||st=='-'||st=='0')
            edges[edges.size()-1].fudetail.push_back(st);
            }
    }
    for(int i=0;i<= (1<<n) -1;i++)
        points.push_back(Po(i,INF));
    
    djs();
    if(points[0].dis==INF) printf("0\n");
        else printf("%d\n",points[0].dis);
    return 0;
}