Minimizing Suffix Modification Cost

You are given two strings a and b of length \(n\)</em> composed of lowercase letters. For a fixed integer \(k\) (with \(1 \le k \le n\)), let \(A\) and \(B\) be the multisets of all substrings of length \(k\) from a and b respectively. (Each multiset contains \(n-k+1\) substrings.)

You are allowed to modify the strings in \(A\) by performing the following operation any number of times:

• Choose any string from \(A\) and replace a contiguous suffix (i.e. the last \(\ell\) characters for some \(1 \le \ell \le k\)) with arbitrary characters. The cost of this operation is the length \(\ell\) of the replaced suffix.

Your goal is to make \(A\) and \(B\) identical as multisets with minimum total cost. Note that you can modify each string in \(A\) independently. For a given string \(x\) from \(A\) and target string \(y\) from \(B\), if the longest common prefix (LCP) of \(x\) and \(y\) is of length \(p\) (i.e. \(x_1 = y_1, x_2 = y_2, \ldots, x_p = y_p\) and either \(p=k\) or \(x_{p+1} \neq y_{p+1}\)), then you can transform \(x\) into \(y\) with a single operation at cost \(k-p\).

Thus, if you assign each string in \(A\) to a unique string in \(B\) (i.e. a permutation matching between the two multisets) and modify it accordingly, the cost to transform \(A_i\) (the \(i\)th substring in \(A\)) into some \(y \in B\) will be \(k-\text{lcp}(A_i, y)\).

Find the minimum total cost required to make \(A\) and \(B\) identical.

Note:

• \(\text{lcp}(x,y)\) denotes the length of the longest common prefix between strings \(x\) and \(y\).

inputFormat

The input consists of three lines:

• The first line contains two integers \(n\) and \(k\) (\(1 \le k \le n\)).
• The second line contains the string a of length \(n\), consisting of lowercase letters.
• The third line contains the string b of length \(n\), consisting of lowercase letters.

outputFormat

Output a single integer, representing the minimum total cost to modify the substrings in \(A\) so that the multiset \(A\) becomes identical to \(B\).

sample

3 2
abc
abd

1