Problem Description

There are two strings $a, b$ of length $n$ consisting of lowercase letters. Take all their substrings of length $k$ (each has $n - k + 1$ substrings). These substrings form multisets $A, B$, respectively. Now you need to modify the strings in $A$ so that $A$ and $B$ become exactly the same.

You may perform the following operation any number of times: choose one string in $A$ and modify a suffix of this string. The cost of this operation is the length of the chosen suffix. The total cost is the sum of the costs of all operations. Find the minimum possible total cost.

Input Format

The first line contains two integers $n, k$, representing the string length and the substring length.
The second line contains a lowercase string $a$.
The third line contains a lowercase string $b$.

Output Format

Output one integer in one line, representing the minimum total cost.

5 3
aabaa
ababa

3

Hint

Sample Explanation

For sample $1$, all substrings are: $A = \{aab, aba, baa\}$, $B = \{aba, bab, aba\}$. You can see that there is one pair of identical substrings $aba$. For the remaining ones, change $aab$ to $aba$ (cost $2$), and change $baa$ to $bab$ (cost $1$). The total cost is $3$.

Constraints

For all testdata, $1 \le k \le n \le 1.5 \times 10^5$.

• For $10\%$ of the testdata, $n \le 11$.
• For another $20\%$ of the testdata, $n \le 200$.
• For another $20\%$ of the testdata, $n \le 2000$.
• For another $10\%$ of the testdata, each character of the strings is uniformly random among lowercase letters.
• For the remaining $40\%$ of the testdata, there are no special restrictions.

Input Format

Output Format

Hint

Translated by ChatGPT 5