[AdditionalFile5635.zip](file://AdditionalFile5635.zip?type=additional_file)

#5635. 「PA 2015 Final」Edycja

标签: 传统 | 时间限制: 10000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2015 Final Edycja

Bajtazar 将他那长度为 $n$ 的网银秘密密码存储在一个名为 haslo.txt 的文本文件中。在听到窗外传来「我们的钱不安全了！」的喊声后，他决定谨慎起见，更改这个已经相当陈旧的密码。于是，Bajtazar 构思了一个同样为 $n$ 位的新密码。为了不忘记它，他现在必须修改密码文件中的内容。

安装在 Bajtazar 电脑上的文本编辑器允许对文件内容进行两种类型的操作：

1. 更改文件内容中的第 $i$ $(1 \leq i \leq n)$ 个字母。
2. 将文件中所有出现的某个选定字母 $x$ 替换为另一个选定字母 $y$ $(x, y \in\{\mathrm{a}, \mathrm{b}, \ldots, \mathrm{z}\})$。

执行一次类型 1 的操作需要 Bajtazar 花费 $1$ 秒。类型 2 的操作需要按下一组复杂的组合键，因此无论选择哪种字母 $x$ 和 $y$，该操作都需要 Bajtazar 花费 $c$ 秒。操作是逐个进行的，每次操作都作用于执行完之前所有操作后的文件内容。

Bajtazar 想知道他最快能在多长时间内完成对文件 haslo.txt 的编辑。

输入格式

输入的第一行包含两个整数 $n$ 和 $c$ $(1 \leq c \leq n \leq 1000000)$，分别表示密码的长度和执行一次类型 2 操作所需的秒数。

第二行和第三行分别包含两个字符串，代表 Bajtazar 的原密码和新密码。

密码由 $n$ 个小写英文字母 $(\texttt{a-z})$ 组成，且两个密码不相同。

输出格式

在一行中输出 Bajtazar 使用类型 1 或类型 2 的操作完成文件编辑所需的最少秒数。

样例

输入

5 2
aaabc
bbbaa

输出

4

位置 $1, 2$ 和 $3$ 的字母可以通过一次类型 2 操作改为正确的字母。位置 $4$ 和 $5$ 的字母通过两次类型 1 操作来更改。