You are working for the International Company for Pool Construction, a construction company which specializes in building swimming pools. A new client wants to build several new pool areas. A pool area is a rectangular grid of \textbf{w}×\textbf{h} square patches, consisting of zero or more (possibly disconnected) pools. A pool consists of one or multiple connected hole patches, which will later be filled with water. In the beginning, you start with a piece of land where each patch is either a hole in the ground ('\textbf{.}') or flat grass ('\textbf{#}'). In order to transform this land into a pool area, you must adhere to the following: \begin{itemize} \item You can leave a patch as it is. This costs nothing. \item If the patch is grass in the beginning, you can dig a hole there. This costs \textbf{d} EUR. \item If the patch is a hole in the beginning, you can fill the hole and put grass on top. This costs \textbf{f} EUR. \item You \textit{must} place special boundary elements along each edge running between a final grass patch and a final hole patch, to ensure that water does not leak from the pool. This costs \textbf{b} EUR per boundary element. \item The outermost rows and columns of the pool area must always be grass. \end{itemize} You are given the task of calculating the cost of the cheapest possible pool area given the layout of the existing piece of land. \InputFile On the first line a positive integer: the number of test cases, at most \textbf{100}. After that per test case: \begin{itemize} \item one line with two integers \textbf{w} and \textbf{h} (\textbf{2} ≤ \textbf{w}, \textbf{h} ≤ \textbf{50}): the width and height of the building site. \item one line with three integers \textbf{d}, \textbf{f} and \textbf{b} (\textbf{1} ≤ \textbf{d}, \textbf{f}, \textbf{b} ≤ \textbf{10000}): the costs for digging a new hole, filling an existing hole, and building a boundary element between a pool and grass patch. \item \textbf{h} lines of \textbf{w} characters each, denoting the layout of the original building site. \end{itemize} \OutputFile Per test case: \begin{itemize} \item one line with an integer: the cost of building the cheapest possible pool area from the original piece of land. \end{itemize}