啊咧……这题不是网络流二十四题么……为啥是个状压dp……
把每一个漏洞看成一个状态，直接硬上状压dp
然后因为有后效型，得用spfa
//minamoto
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
const int N=,M=;
int n,m,tim[M],dp[<<(N-)],vis[<<(N-)],have[M],nhave[M];
int disap[M],appea[M],a[M];
char s1[N],s2[N];queue<int> q;
void init(int x){
for(int i=n-;~i;--i){
switch(s1[i]){
case '+':have[x]|=<<i;break;
case '-':nhave[x]|=<<i;break;
}
switch(s2[i]){
case '+':appea[x]|=<<i;break;
case '-':disap[x]|=<<i;break;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;++i){
scanf("%d%s%s",&a[i],s1,s2);
init(i);
}
memset(dp,0x3f,sizeof(dp));
dp[(<<n)-]=,vis[(<<n)-]=;
q.push((<<n)-);
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=;
for(int i=;i<=m;++i){
if((nhave[i]&(~u))!=nhave[i]) continue;
if((have[i]&u)!=have[i]) continue;
int to=(u&(~disap[i]))|appea[i];
if(dp[to]>dp[u]+a[i]){
dp[to]=dp[u]+a[i];
if(!vis[to]){
vis[to]=,q.push(to);
}
}
}
}
printf("%d\n",dp[]==inf?:dp[]);
return ;
}