Bajtazar stores his secret, $n$-letter internet banking password in a text file named haslo.txt. Upon hearing shouts of "Our money is not safe!" from outside his window, he prudently decided to change his rather old password. Bajtazar has come up with a new password, also $n$ letters long. To avoid forgetting it, he just needs to change the content of the password file.

The text editor installed on Bajtazar's computer allows two types of operations on the file content:

(1) Changing the $i$-th ($1 \le i \le n$) letter of the file content. (2) Changing every occurrence of a chosen letter $x$ in the file to a chosen letter $y$ ($x, y \in \{\text{a, b, . . . , z}\}$).

Performing an operation of type (1) takes Bajtazar 1 second. An operation of type (2) requires pressing a complicated key combination and therefore takes Bajtazar $c$ seconds, regardless of the choice of letters $x$ and $y$.

Operations are performed one by one, and each operation acts on the file content resulting from all previous operations.

Bajtazar wonders how quickly he can edit the haslo.txt file.

Input

The first line of input contains two integers $n$ and $c$ ($1 \le c \le n \le 1\,000\,000$), representing the length of the passwords and the number of seconds required to perform an operation of type (2), respectively. The second and third lines contain strings representing Bajtazar's old and new passwords, respectively. The passwords consist of $n$ lowercase English letters ($\text{a-z}$) and are not identical.

Output

The only line of output should contain the minimum number of seconds Bajtazar needs to edit the file using operations of type (1) or (2).

Examples

Input 1

5 2
aaabc
bbbaa

Output 1

4

Note

The letters at positions 1, 2, and 3 can be changed to the correct ones using one operation of type (2). The letters at positions 4 and 5 are changed using two operations of type (1).