You are given two strings $a$ and $b$ of length $n$ consisting of lowercase letters. Extract all substrings of length $k$ from each (there are $n-k+1$ such substrings for each string), forming sets $A$ and $B$, respectively. You want to modify the strings in $A$ such that $A$ and $B$ become identical as multisets. You may choose to modify a suffix of any string in $A$ any number of times, where the cost of a modification is the length of the suffix. The total cost is the sum of the costs of each modification. Find the minimum total cost required.

Input

The first line contains two integers $n$ and $k$, representing the length of the strings and the length of the substrings, respectively.

The second line contains a string $a$ of lowercase letters.

The third line contains a string $b$ of lowercase letters.

Output

Output a single integer representing the minimum total cost.

Examples

Input 1

5 3
aabaa
ababa

Output 1

3

Note 1

The substrings are: $A = \{aab, aba, baa\}$, $B = \{aba, bab, aba\}$. It can be seen that one pair of $aba$ is already identical. We need to change $aab$ to $aba$ (cost $2$) and $baa$ to $bab$ (cost $1$), for a total cost of $3$.

Constraints

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

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