1211:烦恼的吉安娜

时间限制: 3 S | 内存限制: 65536 KB
Accept: 0 | Submit: 0
[提交] [状态] [讨论版]
描述

吉安娜近来为了联盟与部落之间的战争费劲了脑筋。有一块x行y列的土地上分布着联盟和部落的势力,每一小块区域要么是联盟控制,要么是部落控制。

1、可以耗费a点战争资源疏散某一小块的联盟势力,此时部落将会立刻占领这块联盟撤出的区域;也可以耗费b点战争资源攻下某小块部落占领的区域,改为联盟占领。

2、要求这块土地的边缘区域(第一行和最后一行、第一列和最后一列)必须都是由联盟控制,以形成对部落的包围。

3、在所有联盟和部落的领地边缘盖上防御墙,以保证双方今后不会发生冲突。每一小段防御墙需要耗费c点战争资源。所以,如有有一块区域是部落占领,而这块区域的四周都是联盟占领,那么将会消耗4*c点战争资源来在这块区域的四周盖防御墙。

4、最终联盟的领地没有必要连在一起,部落的领地也没有必要连在一起。

求最节省战争资源的方法。

输入

一个正整数n,表示案例的数量。

每组案例首先是两个正整数x和y,表示区域是x行y列的土地。(2<=x<=50, 2<=y<=50

然后是三个正整数a、b、c,含义见描述。(1<=a,b,c<=10000)

最后是x行y列字符,每个字符表示某块区域是联盟占领还是部落占领,字符A表示联盟占领,字符H表示部落占领。

输出

针对每组案例,输出一个正整数,表示战争资源最少需要的消耗值。

每组案例输出完都要换行。

样例输入

3

3 3

5 5 1

AHA

AHA

AAA

4 5

1 8 1

AHHAA

AAHAA

AHAHA

AAAAA

2 2

27 11 11

AH

HA

样例输出

9

27

22

HINT


来源
第七届编程大赛