8607: BZOJ4607:[PA2015 Final]Edycja

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给定两个长度为n的等长的小写字母串A和B,你可以做以下两种操作: 1.把A中某个位置上的字符修改成另一个字符,用时1秒。比如:ababc变成ababa。 2.把A中某种字符全部修改成另一个种字符,用时c秒。比如:ababc变成acacc。 同一时间只能做一个操作,求把A变成B的最小总耗时。


输入格式

第一行包含两个正整数n,c(1<=c<=n<=1000000),分别表示串长和操作2的代价。 第二行包含一个长度为n的小写字母串A。 第三行包含一个长度为n的小写字母串B。


输出格式

输出一个整数,即把A变成B的最小总耗时。


样例输入

5 2
aaabc
bbbaa

样例输出

4
//先把所有的a都修改成b,然后再把第4个位置的b和第5个位置的c都修改为a。

提示

没有写明提示


题目来源

By Claris

加入题单

上一题 下一题 算法标签: