You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 512.0 MB

Description

You are given a 2d grid of \(N\) rows and \(M\) columns
a pair \((i,j)\) means the cell at the intersection of \(i-th\) row and \(j-th\) column.

At the cell \((1,1)\) there is a water tank and a reservoir at cell \((N,M)\).
Your task is to connect the reservoir with the water tank with the minimum cost.
There are two types of pipe available for this task :

• straight pipe which costs \(x\) taka per unit
• L-shaped pipe which costs \(y\) taka per unit

A pipeline cannot be placed in a cell containing obstacle .Each unit of pipe can cover only one cell of the grid and cannot be divided into multiple pieces. And it is forbidden to bend the pipeline upward(because water doesnt like to flow against gravity :) here is an illustration of an invalid connection :

Calculate the minimum cost needed to make a valid pipeline connection between the water tank and the reservoir or print -1 if it is impossible.

Input

• First line taken an integer \(T\) : number of testcases
• first line of each testcase takes 4 integers \(N,M,x,y\) : number of rows, number of columns, cost of one unit of straight pipe, cost of one unit of L-shaped pipe.
• next \(N\) line each takes \(M\) characters either '#' or '.' (dot)
  where '#' means an obstacle

\(1 <= T <= 10^4\)
\(2 <= N,M <= 2000\)
\(1 <= x,y <= 10^9\)
sum of \(N*M\) over all testcase will not exceed \(4*10^6\)
input file is too large, use fast input output method

Output

for each testcase output the minimum cost of a valid connection. print -1 if it is impossible

Sample input

3
4 3 1 10
. . #
# . .
. . .
. . .
4 3 1 10
. # .
. . .
# . .
. . .
4 3 10 1
. # .
. . .
# . .
. . .

sample output

22
22
4

in the first test case:
two units of straight pipe and two units of L-shape pipe has been used
so the cost is \(2*1 + 2*10 = 22\)

in the second testcase:
two units of straight pipe and two units of L-shape pipe has been used

in the third testcase:
4 L-shaped pipe are used, total cost \(4*1=4\)