Description

Given two lowercase strings A and B of the same length $n$, you may perform the following two operations:

1. Change the character at some position in A to another character, which takes 1 second. For example: ababc becomes ababa.
2. Change all occurrences of some character in A into another character, which takes $c$ seconds. For example: ababc becomes acacc.

You can perform only one operation at a time. Find the minimum total time needed to transform A into B.

Input Format

The first line contains two positive integers $n, c$, representing the string length and the cost of operation 2.

The second line contains a lowercase string A of length $n$.

The third line contains a lowercase string B of length $n$.

Output Format

Output one integer, the minimum total time needed to transform A into B.

5 2
aaabc
bbbaa

4

Hint

Sample Explanation

First, change all a into b, then change the b at position 4 and the c at position 5 into a.

Constraints

For all testdata, $1 \le c \le n \le 10^6$.

Translated by ChatGPT 5