题目描述

小 A 最近一直在找自己的爸爸，用什么办法呢，就是 DNA 比对。

小 A 有一套自己的 DNA 序列比较方法，其最终目标是最大化两个 DNA 序列的相似程度，具体步骤如下：

1. 给出两个 DNA 序列，第一个长度为 $n$，第二个长度为 $m$。
2. 在两个序列的任意位置插入任意多的空格，使得两个字符串长度相同。
3. 逐位进行匹配：
   • 如果两个序列相同位置上的字符都不是空格，假设第一个是 $x$，第二个是 $y$，那么他们的相似程度由 $d(x,y)$ 定义。
   • 对于两个序列中任意一段极长的长度为 $k$ 的连续空格，我们定义这段空格的相似程度为 $g(k) = -A - B(k - 1)$。

最终两个序列的相似程度就是所有的 $d(x,y)$ 加上所有的极长空格段的相似程度之和。

现在小 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

输出 #1

4

说明/提示

样例解释

首先，将序列补成如下形式（- 代表空格）：

ATGG--
AT--CC

然后所有 $d(x,y)$ 的和为 $d(A,A) + d(T,T) = 10$，所有极长连续空格段的相似程度之和为 $g(2) + g(2) = -6$，总和为 4，可以验证，这是相似程度最大的情况。

数据范围

对于所有测试点，有 $0 < B < A \leq 10^3$，DNA 序列仅由字符 A, T, G, C 组成，长度不超过 $10^3$。