Tokyo Olympics Center

You are at a summer training camp for programming contests. The camp is held in a lodging facility called the Tokyo Olympics Center, and today is the last day. You are the one ordered to check whether every participant cleaned their room properly.

The facility is a rectangular field of height $H$ and width $W$, divided into square cells. Rows are numbered $1$ through $H$ from top to bottom, and columns are numbered $1$ through $W$ from left to right. The cell in row $i$ and column $j$ is written $(i, j)$. Two cells are adjacent if they share an edge.

Every cell is either a wall cell or a floor cell. Nobody can enter a wall cell. Floor cells are the inside of the facility, and anyone can move between two adjacent floor cells. The floor cells are divided into units, and each unit has one uppercase letter as its name (A, B, C, ...). A floor cell that is adjacent to exactly one floor cell is a room. Every other floor cell is an aisle.

The figure below shows one facility. A wall cell is written as a single period.

...................
.....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..
...................

In this figure, unit A has $7$ rooms, unit B has $4$ rooms, and unit C has $4$ rooms.

The facility is too large to walk alone, so you asked the other camp participants to check the rooms. Call them staffs. $K$ staffs stand on the cell $(s, t)$, and the check runs as follows.

1. First you assign units to the staffs. Every unit must be assigned to exactly one staff. You may assign every unit to one staff, and you may assign no unit at all to some staffs.
2. Then every staff starts checking the rooms of the assigned units at the same moment. Moving between two adjacent floor cells takes $T_{move}$ time. To check the room $(i, j)$, a staff must move onto the cell $(i, j)$ and spend $T_{check}$ time there. Each staff first decides the order of the assigned units and must then check the rooms in that order. For example, a staff assigned units A, C and E may decide the order E, A, C. That staff must check all rooms of unit E first, then all rooms of unit A, and finally the rooms of unit C. A staff may pass any floor cell. A staff cannot check a room of a unit that was not assigned, and cannot check rooms against the decided order of units.
3. After checking all the assigned rooms, a staff returns to the cell $(s, t)$.
4. When every staff is back on the cell $(s, t)$, the task is done.

All staffs leave at the same moment and move in parallel, so the time of the task is the largest time spent by a single staff. You have to start the next contest soon, so make that time as small as possible.

The first line contains three integers $H$, $W$ and $K$ ($1 \le H \le 50$, $1 \le W \le 50$, $1 \le K \le 12$). The second line contains four integers $s$, $t$, $T_{move}$ and $T_{check}$ ($1 \le s \le H$, $1 \le t \le W$, $1 \le T_{move}, T_{check} \le 10000$).

Each of the following $H$ lines contains exactly $W$ characters describing the cells of the facility. The $j$-th character in the $i$-th of these lines is a single period if the cell $(i, j)$ is a wall cell. Otherwise it is an uppercase letter from A to L, the unit that the cell $(i, j)$ belongs to.

The input satisfies all of the following conditions.

• The number of rooms in each unit is between $1$ and $12$, inclusive.
• The cell $(s, t)$ is an aisle.
• The floor cells of one unit are connected.
• All floor cells of the facility are connected.
• Each unit has at least two cells.

Print the minimum time required to check all the rooms in one line.