挺好的一道题目，我的做法是kmp+Dinic网络流。
kmp求子串在P中出现的次数，从而计算love值。
网络流主要用来处理最优解。
case2中p1的love值是8，p2的love值是7，最终T包含p1和p2，hate值也仅仅算一次。
这个题目难点在于思考为什么网络流的解法是合理，可以反证。从而导出最优解等于love的总和-最大流。
建图方法：
source连接p，初始容量为love值；
p连接s，初始容量为INF;
s连接destination，容量为hate值。
在最优解中，如果s到des的流量小于容量，则证明包含s的p都不被选择。即减去p的容量和。如果流量大于等于容量，则证明该直接去掉hate值。
/* 3505 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 typedef struct {
int l, h, len;
char s[];
int nxt[]; void getnext() {
int i = , j = -; nxt[] = -;
while (i < len) {
if (j==- || s[i]==s[j]) {
++i;
++j;
nxt[i] = j;
} else {
j = nxt[j];
}
}
} int kmp(char *d) {
int dlen = strlen(d);
int i = , j =;
int ret = ; while (i < dlen) {
if (d[i] == s[j]) {
++i;
++j;
} else {
j = nxt[j];
if (j == -) {
j = ;
++i;
}
}
if (j == len) {
++ret;
j = nxt[j];
}
} return ret;
} } node_t; typedef struct {
int v, f, nxt;
} edge_t; const int INF = 0x3f3f3f3f;
const int maxn = ;
const int maxv = maxn * ;
const int maxl = ;
const int maxe = 1e5+;
node_t nd[maxn];
bool M[maxn][maxn];
int score[maxn];
int head[maxv], head_[maxv];
edge_t E[maxe];
int dis[maxv];
int Q[maxv];
char s[maxl];
int nxt[maxl];
int sn, pn, m; int calc(int k) {
int ret = , cnt; rep(i, , sn+) {
cnt = nd[i].kmp(s);
if (cnt) {
ret += nd[i].l * cnt;
M[k][i] = true;
}
} return ret;
} void init() {
m = ;
memset(head, -, sizeof(head));
memset(M, false, sizeof(M));
} void addEdge(int u, int v, int f) {
E[m].v = v;
E[m].f = f;
E[m].nxt = head[u];
head[u] = m++; E[m].v = u;
E[m].f = ;
E[m].nxt = head[v];
head[v] = m++;
} bool bfs(int s, int t) {
int l = , r = ;
int u, v, k; Q[r++] = s;
memset(dis, , sizeof(dis));
dis[s] = ; while (l < r) {
u = Q[l++];
for (k=head[u]; k!=-; k=E[k].nxt) {
v = E[k].v;
if (!dis[v] && E[k].f) {
dis[v] = dis[u] + ;
if (v == t)
return false;
Q[r++] = v;
}
}
} return true;
} int dfs(int u, int t, int val) {
if (u==t || val==)
return val; int ret = ;
int v, tmp; for (int& k=head_[u]; k!=-; k=E[k].nxt) {
v = E[k].v;
if (E[k].f && dis[v]==dis[u]+ && (tmp=dfs(v, t, min(val, E[k].f)))>) {
E[k].f -= tmp;
E[k^].f += tmp;
ret += tmp;
val -= tmp;
if (val == )
return ret;
}
} return ret;
} int Dinic(int s, int t) {
int ret = , tmp; while () {
if (bfs(s, t))
break; memcpy(head_, head, sizeof(head));
while () {
tmp = dfs(s, t, INF);
if (tmp == )
break;
ret += tmp;
}
} return ret;
} void Build() {
int s = ;
int t = maxv - ; rep(i, , sn+) {
addEdge(i, t, nd[i].h);
} rep(i, , pn+) {
addEdge(s, sn+i, score[i]);
rep(j, , sn+) {
if (M[i][j])
addEdge(sn+i, j, INF);
}
}
} int solve() {
int ret = ; rep(i, , pn+) {
scanf("%s", s);
score[i] = calc(i);
ret += score[i];
} Build();
int tmp = Dinic(, maxv-);
ret -= tmp;
#ifndef ONLINE_JUDGE
printf("maxflow = %d\n", tmp);
#endif return ret;
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int t;
int ans; scanf("%d", &t);
rep(tt, , t+) {
init();
scanf("%d %d", &sn, &pn);
rep(i, , sn+) {
scanf("%d %d %s", &nd[i].l, &nd[i].h, nd[i].s);
nd[i].len = strlen(nd[i].s);
nd[i].getnext();
}
ans = solve();
printf("Case %d: %d\n", tt, ans);
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}