Edit Distance Transformation with Group Operation

You are given two strings S₁ and S₂ of lengths n and m respectively, and an integer k. Your task is to compute the minimum number of operations required to transform S₁ into S₂ using the following operations:

• Insertion of a character
• Deletion of a character
• Replacement of a character
• A group operation: if a contiguous block of k characters in S₁ exactly matches the corresponding block of S₂, you can transform the entire block in one operation.

The recurrence relation for the dynamic programming solution is given by:

$$ \textbf{dp}[i][j]=\min\begin{cases} \textbf{dp}[i-1][j] + 1,\\ \textbf{dp}[i][j-1] + 1,\\ \textbf{dp}[i-1][j-1] + \mathbb{1}_{\{S_1[i-1] \neq S_2[j-1]\}},\\ \textbf{dp}[i-k][j-k] + 1 \quad \text{if } i \ge k \text{ and } j \ge k \text{ and } S_1[i-k:i] = S_2[j-k:j] \end{cases} $$

Here, \( \mathbb{1}_{\{condition\}} \) is 0 if the condition is true, and 1 otherwise. Your solution should read the input from stdin and output the result to stdout.

inputFormat

The input consists of four lines:

1. The first line contains two space-separated integers n and m, representing the lengths of the two strings.
2. The second line contains the string S₁.
3. The third line contains the string S₂.
4. The fourth line contains the integer k (the block size for the group operation).

outputFormat

Output a single integer representing the minimum number of operations required to transform S₁ into S₂.

## sample

6 7
kitten
sitting
1

3