AC自动机+状态DP。
虽然很明显的AC自动机+状态DP题，但要分析问题上还是欠缺一点了。一直在犹豫枚举每一个字符选或不选的状态会不会超时，以为会达到状态有2^n，但其实根本没有。因为有很多状态是可以重复的，这是由于每一位字符选或不选，都只能转移动自动机的固定位置，所以，状态是有限的。状态压缩是为了确定必须出现的串是否全部出现。于是可以设状态：
dp[i][j][k]为当前处理到第i个字符，处于自动机的j状态，k为必须出现的字符串是否出现的情况。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int root=0;
const int inf=1<<30;
int trie[1650][26];
int fail[1650];
int tag[1650],tot;
int que[1650],head,tail;
int kill[1650],must[1650],score[1650];
int need;
struct Status{
int act,sc;
void init(){
act=inf,sc=-inf;
}
}dp[2][1650][260];
char str[110];
void init(int cur){
for(int i=0;i<=tot;i++){
for(int k=0;k<(1<<(need+1));k++)
dp[cur][i][k].init();
}
}
void AddTrie(char *s,int sc){
int len=strlen(s);
int i=0,p=root;
while(len--){
if(trie[p][s[i]-'a']==-1){
trie[p][s[i]-'a']=++tot;
kill[tot]=must[tot]=0;
memset(trie[tot],-1,sizeof(trie[tot]));
}
p=trie[p][s[i]-'a'];
i++;
}
if(sc==999){must[p]|=(1<<need);}
else if(sc==-999) kill[p]=1;
else {
score[p]+=sc;
}
}
void build_ac(){
head=tail=0;
que[tail++]=root;
while(head!=tail){
int tmp=que[head++];
int p=-1;
for(int i=0;i<26;i++){
if(trie[tmp][i]!=-1){
if(tmp==root) fail[trie[tmp][i]]=root;
else{
p=fail[tmp];
while(p!=-1){
if(trie[p][i]!=-1){
fail[trie[tmp][i]]=trie[p][i];
break;
}
p=fail[p];
}
if(p==-1) fail[trie[tmp][i]]=root;
}
if(kill[fail[trie[tmp][i]]]) kill[trie[tmp][i]]=1;
if(must[fail[trie[tmp][i]]]) must[trie[tmp][i]]|=must[fail[trie[tmp][i]]];
if(score[fail[trie[tmp][i]]]) score[trie[tmp][i]]+=score[fail[trie[tmp][i]]];
que[tail++]=trie[tmp][i];
}
else{
if(tmp==root) trie[tmp][i]=root;
else{
p=fail[tmp];
while(p!=-1){
if(trie[p][i]!=-1){
trie[tmp][i]=trie[p][i];
break;
}
p=fail[p];
}
if(p==-1) trie[tmp][i]=root;
}
}
}
}
}
void Cal(){
int cur=0,next=1;
init(cur); init(next);
int len=strlen(str);
dp[cur][0][0].act=0; dp[cur][0][0].sc=0;
for(int i=0;i<len;i++){
// cout<<i<<endl;
for(int j=0;j<=tot;j++){
for(int k=0;k<(1<<(need+1));k++){
if(dp[cur][j][k].act>=inf) continue;
int pn=trie[j][str[i]-'a'];
if(kill[pn]){
if(dp[cur][j][k].act+1<dp[next][j][k].act){
dp[next][j][k].act=dp[cur][j][k].act+1;
dp[next][j][k].sc=dp[cur][j][k].sc;
}
else if(dp[cur][j][k].act+1==dp[next][j][k].act&&dp[cur][j][k].sc>dp[next][j][k].sc){
dp[next][j][k].sc=dp[cur][j][k].sc;
}
}
else{
int tmpk=k|must[pn];
if(dp[cur][j][k].act<dp[next][pn][tmpk].act){
dp[next][pn][tmpk].act=dp[cur][j][k].act;
dp[next][pn][tmpk].sc=dp[cur][j][k].sc+score[pn];
}
else if(dp[cur][j][k].act==dp[next][pn][tmpk].act&&dp[cur][j][k].sc+score[pn]>dp[next][pn][tmpk].sc){
dp[next][pn][tmpk].sc=dp[cur][j][k].sc+score[pn];
}
if(dp[cur][j][k].act+1<dp[next][j][k].act ){
dp[next][j][k].act=dp[cur][j][k].act+1;
dp[next][j][k].sc=dp[cur][j][k].sc;
}
else if(dp[cur][j][k].act+1==dp[next][j][k].act&&dp[cur][j][k].sc>dp[next][j][k].sc){
dp[next][j][k].sc=dp[cur][j][k].sc;
}
}
}
}
init(cur);
cur^=1;
next^=1;
}
int minact=inf,maxsc=-inf;
for(int i=0;i<=tot;i++){
if(dp[cur][i][(1<<(need+1))-1].act<minact){
minact=dp[cur][i][(1<<(need+1))-1].act;
maxsc=dp[cur][i][(1<<(need+1))-1].sc;
}
else if(dp[cur][i][(1<<(need+1))-1].act==minact&&maxsc<dp[cur][i][(1<<(need+1))-1].sc)
maxsc=dp[cur][i][(1<<(need+1))-1].sc;
}
if(minact>=inf)
puts("Banned");
else cout<<minact<<" "<<maxsc<<endl;
}
int main(){
int T,icase=0;
char s[20];int sc;
scanf("%d",&T);
while(T--){
int n;
tot=0,need=-1;
memset(trie[tot],-1,sizeof(trie[tot]));
memset(score,0,sizeof(score));
memset(kill,0,sizeof(kill));
memset(must,0,sizeof(must));
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s%d",s,&sc);
if(sc==999) need++;
AddTrie(s,sc);
}
// cout<<"YES"<<endl;
build_ac();
scanf("%s",str);
printf("Case %d: ",++icase);
Cal();
}
return 0;
}