P15727 [JAG 2023 Summer Camp #3] Edit distance on table

You have a table with $H$ rows and $W$ columns. Each cell of the table contains a letter. You are going to construct a string by the following steps. - Step 1: Pick up a cell in the table and let $S$ be a string of length $1$ containing the letter in the cell. - Step 2: Do either - stop building $S$, or - select a cell from four cells which shares an edge with the current one. Then, append the letter in the cell to $S$, and move to the cell. Then, repeat step 2. You also have a string $T$. Your mission is to minimize the edit distance between $S$ and $T$. The edit distance (also known as Levenshtein distance) between string $U$ and $V$ is the minimum number of steps required to convert $U$ into $V$ by using the following operations. - Replace a character in $U$ with another one. - Insert a character into $U$. - Delete a character from $U$.

The input consists of a single test case in the following format. $$ \begin{aligned} &H \ W \\ &c_{1,1} c_{1,2} \ldots c_{1,W} \\ &c_{2,1} c_{2,2} \ldots c_{2,W} \\ &\vdots \\ &c_{H,1} c_{H,2} \ldots c_{H,W} \\ &T \end{aligned} $$ $H$ and $W$ ($2 \leq H, W \leq 100$) represents the height and the width of the table respectively. $c_{i,j}$ ($1 \leq i \leq H$, $1 \leq j \leq W$) is a character in the cell in the $i$-th row and the $j$-th column. $T$ is a non-empty string. The length of $T$ doesn't exceed $2,000$. $c_{i,j}$ and $T$ consist of lowercase English letters.

Output the minimum possible edit distance between $S$ and $T$ in one line.