[PA 2015 Final] Edycja
题目描述
给定两个长度为 $n$ 的等长的小写字母串 A 和 B,你可以做以下两种操作:
1. 把 A 中某个位置上的字符修改成另一个字符,用时 1 秒。比如:```ababc``` 变成 ```ababa```。
2. 把 A 中某种字符全部修改成另一个种字符,用时 $c$ 秒。比如:```ababc``` 变成 ```acacc```。
同一时间只能做一个操作,求把 A 变成 B 的最小总耗时。
输入输出格式
输入格式
第一行包含两个正整数 $n,c$,分别表示串长和操作 2 的代价。
第二行包含一个长度为 $n$ 的小写字母串 A。
第三行包含一个长度为 $n$ 的小写字母串 B。
输出格式
输出一个整数,即把 A 变成 B 的最小总耗时。
输入输出样例
输入样例 #1
5 2
aaabc
bbbaa
输出样例 #1
4
说明
#### 样例解释
先把所有的 a 都修改成 b,然后再把第 4 个位置的 b 和第 5 个位置的 c 都修改为 a。
#### 数据范围
对于所有数据,满足 $1\le c\le n\le10^6$。