Description

The most mysterious organization in Chani is “Related Department”. It is related to almost everything, and has branches almost everywhere. Events always have relation with it. Whenever disasters happen, “Related Department” would stand out to commit its responsibility. The members of “Related Department” are called “Related person”. However, ordinary people have no idea about who is “Related person” since their information is national secret.
Xiaoming is the top typist in Chani. The legend is that he could type 400 words per minute. Today he accepted an order from a man who said that he is a “Related person”. That “Related person” asked Xiaoming to turn many paper documents into electronic files. For reasons of security, Xiaoming has to use a special device which has limited functions. With the special device, Xiaoming can only perform such operations:
1. Creating a new file. It takes a quite short time that we ignore the time for it.
2. Replacing current file with some file finished before. A file is allowed to be used to replace another one only after it is finished and won’t be edited later.
3. Deleting any letter(s) in current file.
4. Inserting letter(s) at arbitrary position in current file.
Note that, the keyboard for this device is so strange that the time for typing different letter may be different.
Xiaoming is somewhat afraid of dealing with “Related person”, so he wants to accomplish this order as soon as possible. Knowing time needed for each operation, Xiaoming is trying to make the best plan which spends the minimum time.

Input

The first line of the input is T (no more than 50), which stands for the number of test cases you need to solve.
Each case begins with two integers, repCost and delCost (1 <= repCost, delCost <= 50), time needed to replace current file, time for deleting one letter. On the second line, there are 26 numbers representing the time for typing each letter from ‘a(chǎn)’ to ‘z’, each number is between 1 and 50.
Then a line with an integer N (1 <= N <= 50) is given indicating the number of files.
N lines followed. Each line gives a string only consisting of letters ‘a(chǎn)’-‘z’ to represent a file. The maximum length of the strings is not greater than 50.

Output

For every test case, you should output "Case #k: c" first in a line, where k indicates the case number and counts from 1, c is the minimum time needed.

Simple Input

2
1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
aaab
aaaa
10 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
aaab
aaaa

Simple Output

Case #1: 7
Case #2: 8

**************************************************************

題目大意：某個打字員要打n個字符串，有如下操作：

　　1.創(chuàng)建一個一個文件，不計時間。

　　2.用一個已經(jīng)存在的文件替換當(dāng)前文件，花費(fèi)為rep

　　3.刪除某些字符，每刪除一個字符的花費(fèi)為del

　　4.在當(dāng)前文件任意位置增加字符，花費(fèi)為val[字符]。

求打完這些字符串所要的最小花費(fèi)。

解題思路：這道題，怎么說呢。我們把每個字符串當(dāng)一個節(jié)點(diǎn)，一個字符串到另一個字符串的變化花費(fèi)計算出來，然后再有一個最終節(jié)點(diǎn)連到所有的字符串，權(quán)值為打這個字符串的花費(fèi)。那么，問題轉(zhuǎn)化為這個有向圖中的最小樹形圖。建圖很簡單，求最小樹形圖也不過是套用朱劉算法的模板，然而令人糾結(jié)的是怎么把一個字符串變化到另一個字符串的花費(fèi)，要不是這個，我也不會寫這道題。這個花費(fèi)很難算啊，經(jīng)過我、YYB、ZYC一個晚上的思考，終于相處了這個dp過程，真是艱辛苦楚。

直接考慮s1變化到s2的dp：

dp[0][1~len1]=del*len1代表全部刪除，以后一個一個匹配進(jìn)來。

dp[i][0]=dp[i-1][0]+val[i];

dp[i][j],當(dāng)s1的第i個==s2的第j個字母，dp[i][j]=dp[i-1][j-1]-del;當(dāng)s1的第i個!=s2的第j個字母,dp[i][j]=min(dp[i][j-1],dp[i-1][j]+val[i]);

dp很難想 真心的。

        //#pragma comment(linker, "/STACK:65536000")

#include <map>

#include <stack>

#include <queue>

#include <math.h>

#include <vector>

#include <string>

#include <fstream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <algorithm>

#define N 55

#define M 30

#define E

#define inf 0x3f3f3f3f

#define dinf 1e10

#define linf (LL)1<<60

#define eps 1e-8

#define LL long long

#define clr(a,b) memset(a,b,sizeof(a))

#define D(a) ((a)*(a))

using namespace std;



int n;

int del,rep,val[M],gra[N][N];

string s[N];

int dp[N][N];

int pre[N],vis[N],cnt,ced[N];//ced數(shù)組用來縮點(diǎn)用的



void dpt(int a,int b)

{

    string s1=s[a],s2=s[b];

	int len1=s1.size(),len2=s2.size();

	for(int i=0;i<=len1;i++)dp[0][i]=len1*del;

	for(int i=1;i<=len2;i++)

    {

        dp[i][0]=dp[i-1][0]+val[s2[i-1]-'a'];

        for(int j=1;j<=len1;j++)

            if(s1[j-1]==s2[i-1])

                dp[i][j]=dp[i-1][j-1]-del;

            else

                dp[i][j]=min(dp[i][j-1],dp[i-1][j]+val[s2[i-1]-'a']);

    }

    gra[a][b]=dp[len2][len1]+rep;

}



void dfs(int s)//dfs判是否有解

{

    vis[s]=1;cnt++;

    for(int i=1;i<=n;i++)

        if(gra[s][i]<dinf&&!vis[i])

            dfs(i);

}



int ZHULIU(void)

{

    clr(ced,0);int ans=0;

    int i,j,k;

    do

    {

        for(i=2;i<=n;i++)//清除自環(huán)，以及求每個點(diǎn)的入邊

        {

            if(ced[i])continue;

            pre[i]=1;

            for(j=2;j<=n;j++)

                if(j!=i&&!ced[j]&&gra[pre[i]][i]>gra[j][i])

                    pre[i]=j;

        }

        for(i=2;i<=n;i++)

        {

            if(ced[i])continue;

            clr(vis,0);

            for(j=i;j!=1&&!vis[j];j=pre[j])vis[j]=1;//尋找環(huán)，被vis標(biāo)記的是環(huán)內(nèi)的點(diǎn)

            if(j==1)continue;

            ans+=gra[pre[j]][j];

            for(i=pre[j];i!=j;i=pre[i])//把環(huán)里的權(quán)值加到ans中去

                ans+=gra[pre[i]][i],ced[i]=1;

            for(k=1;k<=n;k++)//這個和下面那個for在縮點(diǎn)

                if(!ced[k]&&gra[k][j]<inf)

                    gra[k][j]-=gra[pre[j]][j];

            for(i=pre[j];i!=j;i=pre[i])

                for(k=1;k<=n;k++)

                {

                    if(ced[k])continue;

                    gra[j][k]=min(gra[j][k],gra[i][k]);

                    if(gra[k][i]<inf)

                        gra[k][j]=min(gra[k][j],gra[k][i]-gra[pre[i]][i]);

                }

            break;

        }

    }while(i<=n);

    for(int i=2;i<=n;i++)//把不是剩下的入邊都加上

        if(!ced[i])ans+=gra[pre[i]][i];

    return ans;

}



void re(void)

{

	cin>>rep>>del;

	for(int i=0;i<26;i++)cin>>val[i];

	cin>>n;n++;

	for(int i=2;i<=n;i++)

        cin>>s[i];

}



void run(void)

{

	for(int i=2;i<=n;i++)

        for(int j=2;j<=n;j++)

            gra[i][j]=inf;

    for(int i=2;i<=n;i++)

        for(int j=2;j<=n;j++)

            if(i!=j)

                dpt(i,j);

    for(int i=2;i<=n;i++)

    {

        int a=0,len=s[i].size();

        for(int j=0;j<len;j++)a+=val[s[i][j]-'a'];

        gra[1][i]=a;

    }

    cout<<ZHULIU()<<endl;

}



int main()

{

    //freopen("d:\\in.txt","r",stdin);

	int ncase;

	scanf("%d",&ncase);

	for(int i=1;i<=ncase;i++)

	{

		re();

		cout<<"Case #"<<i<<": ";

		run();

	}

	return 0;

}