| 描述 |
|---|
吉安娜近来为了联盟与部落之间的战争费劲了脑筋。有一块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 |
| 来源 |
| 第七届编程大赛 |