You have a table with rows and 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 be a string of length containing the letter in the cell.
Step 2: Do either
stop building , or
select a cell from four cells which shares an edge with the current one. Then, append the letter in the cell to , and move to the cell. Then, repeat step 2.
You also have a string . Your mission is to minimize the edit distance between and .
The edit distance (also known as Levenshtein distance) between string and is the minimum number of steps required to convert into by using the following operations.
Replace a character in with another one.
Insert a character into .
Delete a character from .
输入格式
The input consists of a single test case in the following format.
and () represents the height and the width of the table respectively. (, ) is a character in the cell in the -th row and the -th column. is a non-empty string. The length of doesn't exceed . and consist of lowercase English letters.
输出格式
Output the minimum possible edit distance between and in one line.
