1 #include<stdio.h>
 2 #include<string.h>
 3 #include<map>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAX(x,y)(x>y?x:y)
 7 const int MAXN=2100;
 8 int dp[2][MAXN];
 9 char a[MAXN],b[MAXN],c[MAXN];
10 map<char,int>mp;
11 int main(){
12     int N,temp;
13     while(~scanf("%d",&N)){
14         memset(dp,0,sizeof(dp));
15         mp.clear();
16         scanf("%s",a+1);
17         for(int i=1;i<=N;i++){
18             scanf("%d",&temp);
19             mp[a[i]]=temp;
20         }
21         scanf("%s",b+1);
22         scanf("%s",c+1);
23         int t1,t2;
24         t1=strlen(b+1);t2=strlen(c+1);
25         for(int i=1;i<=t1;i++)
26             for(int j=1;j<=t2;j++)
27                 if(b[i]==c[j])
28                     dp[i&1][j]=dp[(i-1)&1][j-1]+mp[b[i]];
29                     else{
30                         int k=MAX(dp[(i-1)&1][j],dp[i&1][j-1]);
31                         dp[i&1][j]=MAX(k,dp[(i-1)&1][j-1]);
32                     }
33                     printf("%d\n",dp[t1&1][t2]);
34     }
35     return 0;
36 }