Задачі
Pool construction
Pool construction
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}
Вхідні дані #1
3 3 3 5 5 1 #.# #.# ### 5 4 1 8 1 #..## ##.## #.#.# ##### 2 2 27 11 11 #. .#
Вихідні дані #1
9 27 22