题意繁琐，实际是先求原串由给定串组成后的最大花费，再求得到这个最大花费的最小串的总长度
具体题意请看题：AIZU 2130
/*author: birdstorm*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <complex>
#include <set>
#include <algorithm>
#include <climits>
#include <cfloat>#define MAXN 1005
//#define N 105
#define inf 1.0e20
//#define eps 1.0e-8
#define MOD 1000000007#define pb push_back
#define mp make_pair
#define next(i) (i+1)%sz#define For(i,m,n) for(int i=(m);i<(n);i++)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define rep(i,m,n) for(int i=(m);i<=(n);i++)
#define repd(i,m,n) for(int i=(m);i>=(n);i--)
#define LL long long
#define testusing namespace std;const double eps=1.0e-8;
const double pi=acos(-1.0);
string s[MAXN];
string ans;
int n, len[MAXN], cs=1;
int a[MAXN], dp[MAXN], dp2[MAXN];
int main()
{while(scanf("%d",&n),n){For(i,0,n){cin>>s[i]>>a[i];len[i]=s[i].length();}cin>>ans;int length=ans.length();rep(i,0,length) dp[i]=-0x3f3f3f3f;dp[0]=0;rep(i,0,length){For(j,0,n){int End=i-len[j];if(End>=0&&dp[End]>=0&&ans.substr(End,len[j])==s[j]){dp[i]=max(dp[i],dp[End]+a[j]); //cout<<i<<" "<<s[j]<<endl;}}}int sz=dp[length];rep(i,0,sz) dp2[i]=0x3f3f3f3f;dp2[0]=0;For(i,0,n){rep(j,0,sz-a[i]){dp2[j+a[i]]=min(dp2[j+a[i]],dp2[j]+len[i]);}}printf("Case %d: %d\n",cs++,dp2[sz]);}return 0;
}