问题描述

你正在参加编程竞赛夏季训练营。训练营在一个名为"东京奥林匹克中心"的住宿设施中举行。今天是训练营的最后一天。不幸的是，你被要求检查所有参与者是否正确清理了房间。

住宿设施是一个高度为$H$，宽度为$W$的矩形场地。场地被划分成方格。行从上到下依次编号为1到$H$，列从左到右依次编号为1到$W$。第$i$行第$j$列的单元格表示为$(i, j)$。如果两个单元格共享一条边，则它们是相邻的。

每个单元格可以是"墙单元格"或"地板单元格"。墙单元格表示无法进入的墙。地板单元格是住宿设施内部的一部分。每个人都可以在相邻的两个地板单元格之间移动。地板单元格分为若干个组。每个组被分配一个大写英文字母（A,B,C...）。仅与一个地板单元格相邻的地板单元格称为"房间"。否则，地板单元格称为"过道"。例如，住宿设施可以显示为以下图示。我们用.（一个句点）表示墙单元格。

...................
.....AAABBBBBBB....
...A.AA.A...B.B..B.
..AAAAAAAABBBBBBBB.
...A..A.A.....B....
......A.......BBBB.
....A.AA..C.C...B..
...AAAAACCCCCCBBBB.
...A..A...C.C...B..
...................```

在上面的图示中，单元A有7个房间，单元B有4个房间，单元C有4个房间。

由于住宿设施太大，无法单独探索，所以你请其他训练营的参与者检查房间。为了简化起见，我们称他们为"工作人员"。现在，有$K$名工作人员在单元$(s, t)$的单元格上。你决定按照以下步骤检查房间。

1. 首先，你将每个工作人员分配给一些单元。每个单元必须分配给一个工作人员。请注意，可以将所有单元都分配给一个工作人员，或者不分配给某些工作人员。
    
2. 然后，每个工作人员同时开始检查分配给他们的单元的房间。工作人员可以在$T_{\text{move}}$时间内在两个相邻的地板单元格之间移动。要检查$(i, j)$处的房间，工作人员必须移动到$(i, j)$处并在那里花费$T_{\text{check}}$时间。每个工作人员首先确定要检查的单元的顺序，并且必须按照顺序检查房间。例如，假设有一个分配了单元A、C和E的工作人员。他可能决定顺序为E->A->C。然后，他必须首先检查单元E中的所有房间。然后，他必须检查单元A中的所有房间，依此类推。工作人员可以通过任何地板单元格。但是，工作人员不能检查未分配给他们的房间。此外，工作人员不能违反他们已经决定的单元顺序检查房间。
    
3. 在检查完所有分配的房间后，工作人员必须返回到单元格$(s, t)$。
    
4. 当每个工作人员都返回到单元格$(s, t)$时，任务完成。

由于时间不足，无法参加下一场比赛，你希望尽量减少检查所有房间所需的总时间。

* * *

### 输入

输入的第一行包含三个整数$H$，$W$和$K$（$1\le H\le 50$，$1\le W\le 50$，$1\le K\le 12$）。第二行包含四个整数$s$，$t$，$T_{\text{move}}$和$T_{\text{check}}$（$1\le s\le H$，$1\le t\le W$，$1\le T_{\text{move}},T_{\text{check}}\le 10,000$）。接下来的$H$行每行都包含$W$个字符。每个字符表示住宿设施中的一个单元格。这些行中的第$i$行第$j$个字符如果单元格$(i, j)$是墙单元格，则为`.`。否则，该字符是一个大写英文字母（`A`-`L`），表示单元格$(i, j)$所属的单元。

你可以假设满足以下条件。

* 每个单元中的房间数量在1到12之间（包括1和12）。
    
* 单元格$(s, t)$保证是过道。
    
* 每个单元中的地板单元格是连接的。
    
* 场地中的地板单元格是连接的。
    
* 每个单元包含至少两个单元格。

### 输出

输出一行，表示检查所有房间所需的最短时间。

* * *

### 示例输入1

```plain
3 3 1
1 1 10 10
AAA
A..
A..```

### 示例输出1

```plain
100```

* * *

### 示例输入2

```plain
3 3 2
1 1 10 10
ABB
A..
A..```

### 示例输出2

```plain
50```

* * *

### 示例输入3

```plain
5 10 3
3 6 1 100
...G.H.A..
.AAGAHAABB
FFAAAAAAA.
.EEAAADACC
..E...D...```

### 示例输出3

```plain
316```

* * *

### 示例输入4

```plain
10 19 2
6 15 3 10
...................
.....AAABBBBBBB....
...A.AA.A...B.B..B.
..AAAAAAAABBBBBBBB.
...A..A.A.....B....
......A.......BBBB.
....A.AA..C.C...B..
...AAAAACCCCCCBBBB.
...A..A...C.C...B..
...................```

### 示例输出4

```plain
232```

* * *

### 示例输入5

```plain
27 36 6
24 19 616 1933
....................................
..........B...............B.........
..........BBB..........BBBB.........
..........BBBBB.......BBBB..........
...........BBBBBBBBBBBBBBB..........
...........BBBBBBBBBBBBBBB..........
...........BBBBBBBBBBBBBB...........
............BBBBBBBBBBBBB...........
...........BBBBBBBBBBBBBBB..........
..........BBBBBBBBBBBBBBBBB.........
......B...BBBBBBBBBBBBBBBBB...B.....
......BB.BBBBBBBBBBBBBBBBBB..BB.....
.......BBBBBBBBBBBBBBBBBBBB.BB......
.........BBBBBBBBBBBBBBBBBBBB.......
........BBBBB..BBBBBBBB..BBBBB......
......BBBBBB....BBBBB....BBBBBB.....
.....BBBBBBBB...BBBBB..BBBBBBBB.B...
...BBBBBBB..B...BBBBB..B..BBBBBBBB..
.BBBBBBBBB.....BBBBBBB......BBBBBBB.
..BBBBBBB......BBBBBBB........BBB...
.BBBB.........BBBBBBBBB........BBB..
..............BBBBBBBBB.............
.............BBBBBBBBBB.............
.............BBBBBBBBBB.............
..............BBBBBBBB..............
..............BBBBBBBB..............
....................................```

### 示例输出5

```plain