你有一个 $H$ 行 $W$ 列的表格，每个单元格中包含一个字母。 你将通过以下步骤构造一个字符串：

1. 在表格中任选一个单元格作为当前单元格。
2. 令 $S$ 为一个长度为 1 的字符串，其内容为起始单元格中的字母。
3. 执行以下任一操作：
   • 停止构造 $S$，或者
   • 选择一个与当前单元格共享边的单元格（最多有四个这样的单元格）。移动到该单元格（将其作为当前单元格），并将该单元格中的字母追加到 $S$ 的末尾。之后，重复步骤 3。

你还有一个字符串 $T$。你的任务是最小化 $S$ 和 $T$ 之间的编辑距离。 编辑距离（也称为 Levenshtein 距离）是指将字符串 $U$ 转换为 $V$ 所需的最少步骤数。每一步可以是以下操作之一：

• 将 $U$ 中的一个字符替换为另一个字符。
• 在 $U$ 中插入一个字符。
• 从 $U$ 中删除一个字符。

输入格式

第一行包含两个整数 $H$ 和 $W$：表格的高度和宽度（$2 \le H, W \le 100$）。 接下来的 $H$ 行，每行包含 $W$ 个小写英文字母，共同构成该表格。 最后一行包含字符串 $T$，由小写英文字母组成（$1 \le |T| \le 2000$）。

输出格式

输出一行，包含一个整数：$S$ 和 $T$ 之间可能的最小编辑距离。

样例

样例输入 1

2 2
ab
ar
abracadabra

样例输出 1

2