Edit distance on table

A table has $H$ rows and $W$ columns. Each cell contains one lowercase English letter.

Build a string with the following steps.

1. Pick a cell and let $S$ be a string of length 1 containing the letter in that cell.
2. Choose one of the following.
   • Stop building $S$.
   • Choose one of the four cells that share an edge with the current cell. Append its letter to $S$, move to that cell, and repeat step 2.

You are given a string $T$. Your goal is to minimize the edit distance between $S$ and $T$.

The edit distance between strings $U$ and $V$ is the minimum number of operations needed to turn $U$ into $V$. The allowed operations are:

• Replace one character with another.
• Insert one character.
• Delete one character.

The first line contains $H$ and $W$. Each of the next $H$ lines describes one row of the table. The last line contains the string $T$. $T$ is not empty and its length is at most $2000$. The letters in the table and $T$ are all lowercase English letters.

Print the minimum possible edit distance between $S$ and $T$ on one line.