Building a Swimming Pool

Time limit2.5sMemory limit128 MB

Summary

Compute the minimum cost to convert a grid into grass/hole cells, forcing the border to be grass and charging per boundary edge between grass and hole.

Level: Easy3 of 10
Topics: Array, Greedy, Implementation
Solved: No attempts yet

Problem

Sanggeun is building a swimming pool in Jeongin's front yard.

The pool site is $w$ columns wide and $h$ rows tall, divided into $1 \times 1$ square cells. A pool consists of $0$ or more hole cells, which will later be filled with water.

Before construction, each cell is either a hole (.) or grass (#). Turning the site into a pool must follow these rules:

Leaving a cell unchanged costs nothing.
Digging a hole in a grass cell costs $d$ .
Filling a hole cell and planting grass costs $f$ .
Every edge on the pool's boundary — that is, every edge where a grass cell meets a hole cell — must be sealed so that water cannot leak, at a cost of $b$ per edge.
In the finished site, every cell in the outermost row and outermost column must be grass.

Given the initial state of the site, write a program that computes the minimum cost to finish the pool.

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 100$ )

For each test case, the first line contains the site dimensions $w$ and $h$ , separated by a space. ( $2 \le w, h \le 50$ ) The second line contains three integers $d$ , $f$ , and $b$ . ( $1 \le d, f, b \le 10000$ ) The next $h$ lines describe the initial state of the site; each line consists of $w$ characters, where # denotes grass and . denotes a hole.

Output

For each test case, print the minimum cost to finish the pool on its own line.

Examples8

Example 1

Input

3
3 3
5 5 1
#.#
#.#
###
5 4
1 8 1
#..##
##.##
#.#.#
#####
2 2
27 11 11
#.
.#

Expected output

9
27
22

Example 2
Input
```
1
4 4
3 4 5
####
####
####
####
```
Expected output
```
0
```
Example 3
Input
```
1
2 2
1 1 1
..
..
```
Expected output
```
4
```
Example 4
Input
```
1
3 3
100 100 1
###
#.#
###
```
Expected output
```
4
```
Example 5
Input
```
1
3 3
100 1 100
###
#.#
###
```
Expected output
```
1
```
Example 6
Input
```
1
5 3
1 100 100
#####
#.#.#
#####
```
Expected output
```
200
```

Example 7

Input

1
4 4
10000 10000 10000
#..#
.##.
.##.
#..#

Expected output

Example 8

Input

5
2 2
5 5 5
##
##
3 3
2 3 4
###
#.#
###
4 3
6 1 9
####
#..#
####
3 4
9 9 1
###
#.#
#.#
###
5 5
3 7 2
#####
#.#.#
#...#
#.#.#
#####

Expected output