Building a Swimming Pool

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.

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.

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