pos=0,newnode();
tot=0;
for(i=1;i<=n;i++){
scanf("%s %d",s,&score);
insert(s,score);
}
makefail();
scanf("%s",s);
printf("Case %d: ",t);
makeans();
}
return 0;
}
#include
#include
#include
#include
#define N 1700
using namespace std;
const int INF=-((~(0U))>>1);
char s[110];
int score;
int next[N][26],pos,flag[N],sta[N],val[N],fail[N],tot;
int newnode(){
memset(next[pos],0,sizeof(next[pos]));
flag[pos]=fail[pos]=sta[pos]=val[pos]=0;
return pos++;
}
void insert(char * s,int score){
int p=0,i;
for(i=0;s[i];i++){
int k=s[i]-'a';
p=next[p][k] next[p][k]:next[p][k]=newnode();
}
if(score==999){
flag[p]=1;
sta[p]=(1<
}
else if(score==-999){
flag[p]=-1;
}
else{
flag[p]=2;
val[p]=score;
}
}
void makefail(){
queue
q.push(0);
int i,p=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(i=0;i<26;i++){
int v=next[u][i];
if(v==0) next[u][i]=next[fail[u]][i];
else q.push(v);
if(u&&v){
fail[v]=next[fail[u]][i];
if(flag[fail[v]]==-1){
flag[v]=-1;
}
else if(flag[v]!=-1){
sta[v]|=sta[fail[v]];
val[v]+=val[fail[v]];
}
}
}
}
}
int dp[2][260][N];
int cost[2][260][N];
void makeans(){
int i,j,k,len,cur;
len=strlen(s);
cur=1;
for(j=0;j<(1<
dp[0][0][0]=0;
cost[0][0][0]=0;
for(i=0;s[i];i++){
for(j=0;j<(1<
for(j=0;j<(1<
if(dp[cur][j][k]>dp[cur^1][j][k]+1){
dp[cur][j][k]=dp[cur^1][j][k]+1;
cost[cur][j][k]=cost[cur^1][j][k];
}
else if(dp[cur][j][k]==dp[cur^1][j][k]+1){
cost[cur][j][k]=max(cost[cur][j][k],cost[cur^1][j][k]);
}
}
}
for(j=0;j<(1<
int v=next[k][s[i]-'a'];
if(flag[v]==-1)continue;
//if((j|sta[v])==((1<
dp[cur][j|sta[v]][v]=dp[cur^1][j][k];
cost[cur][j|sta[v]][v]=cost[cur^1][j][k]+val[v];
}
else if(dp[cur][j|sta[v]][v]==dp[cur^1][j][k]){
cost[cur][j|sta[v]][v]=max(cost[cur][j|sta[v]][v],cost[cur^1][j][k]+val[v]);
}
}
}
cur^=1;
}
int ans1=-INF;
int ans=INF;
for(j=0;j
else if(dp[cur^1][(1<
}
if(ans1!=-INF){
printf("%d %d\n",ans1,ans);
return ;
}
printf("Banned\n");
}
int main(){
int t,T,