2727: 游戏达人
题目描述
在这个活动中，每一位参赛选手会得到两个清单$X$和$Y$， 第$i$次行动中，他需要先游玩$X_i$，然后游玩$Y_i$，并获得$d(X_i,Y_i)$积分
由于获得的积分可能为负，所以选手们可以在清单中的任意位置插入代号非$A,C,G,T$的任意游戏，只要两个清单长度一致即可
这样的话，对于任意的$X_i$和$Y_i$，如果有任意一个不是$A,C,G,T$中的一个，就不会计算积分
但这样做也是有代价的：若在任意位置连续插入了$k$个其他游戏，那么就会被扣除$e(k)$积分（$e(k)=x+y(k-1)$，$x,y$为常量）
因为积分第一可以获得神秘奖品，现在小A想知道，他能拿到的最大积分是多少
输入
输入第$1$行一个字符串，表示清单$X$。
输入第$2$行一个字符串，表示清单$Y$。
接下来$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)$
最后一行两个用空格隔开的正整数$x,y$，意义如题中所述。
输出
样例输入 复制
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(A,A)+d(T,T)=10$
扣除的积分共为$ e(2)+e(2)=6$
共得到$4$积分，这是获得积分最多的情况。
【数据范围】
对于所有测试点，有$0<y<x<1000$, $-1000 < d(A,B) < 1000$
$d(A, B)=d(B, A)$，字符串中只包含$A,T,G,C$四种字符。
|
测试点编号
|
n+m 的范围
|
特殊约定
|
|
$1$
|
$n=m=1$
|
无特殊要求
|
|
$2$
|
$n+m≤15$
|
|
|
$3$
|
$n+m≤300$
|
|
|
$4$
|
||
|
$5$
|
$n+m≤3000$
|
序列中只包含一种字符
|
|
$6$
|
无特殊要求
|
|
|
$7$
|
||
|
$8$
|
||
|
$9$
|
||
|
$10$
|