找爸爸
题号：NC14499
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

小A最近一直在找自己的爸爸，用什么办法呢，就是DNA比对。
小A有一套自己的DNA序列比较方法，其最终目标是最大化两个DNA序列的相似程度，具体步骤如下：

1.给出两个DNA序列，第一个长度为,第二个长度为.
2.在两个序列的任意位置插入任意多的空格，使得两个字符串长度相同
3.逐位进行匹配，如果两个序列相同位置上的字符都不是空格,假设第一个是,第二个是,那么他们的相似程度由定义。对于两个序列中任意一段极长的长度为
的连续空格，我们定义这段空格的相似程度为。
那么最终两个序列的相似程度就是所有的加上所有的极长空格段的相似程度之和。
现在小A通过某种奥妙重重的方式得到了小B的DNA序列中的一段，他想请你帮他算一下小A的DNA序列和小B的DNA序列的最大相似程度。

输入描述:

输入第1行一个字符串，表示小A的DNA序列。
输入第2行一个字符串，表示小B的DNA序列。
接下来4行，每行4个整数，用空格隔开，表示d数组，具体顺序如下所示。
d(A,A) d(A,T) d(A,G) d(A,C)
d(T,A) d(T,T) d(T,G) d(T,C)
d(G,A) d(G,T) d(G,G) d(G,C)
d(C,A) d(C,T) d(C,G) d(C,C)
最后一行两个用空格隔开的正整数A,B，意义如题中所述。

输出描述:

输出共一行，表示两个序列的最大相似程度。
示例1

输入

复制 
ATGG
ATCC
5 -4 -4 -4 
-4 5 -4 -4 
-4 -4 5 -4 
-4 -4 -4 5 
2 1

输出

复制 
4

说明

首先，将序列补成如下形式（”-“代表空格）
ATGG—
AT—CC
然后所有d(x,y)的和为d(A,A)+d(T,T)=10
所有极长连续空格段的相似程度之和为g(2)+g(2)=-6
总和为4，可以验证，这是相似程度最大的情况。

备注:

对于所有测试点，有n+m≤3000,0< B<A <=1000, -1000<= d(x,y)<= 1000,d(x,y)=d(y,x)，序列只包含{A,T,G,C}四种字符。