P6700 [PA 2015 Final] Edition

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.

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 one integer, the minimum total time needed to transform A into B.

#### 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