有两个长度为 n 的由小写字母组成的字符串 a,b,取出他们所有长为 k 的子串(各有 n−k+1 个),这些子串分别组成集合 A,B。现在要修改 A 中的串,使得 A 和 B 完全相同。可以任意次选择修改 A 中一个串的一段后缀,花费为这段后缀的长度。总花费为每次修改花费之和,求总花费的最小值。
输入格式
第一行两个整数 n,k 表示字符串长度和子串长度;
第二行一个小写字母字符串 a;
第三行一个小写字母字符串 b。
输出格式
输出一行一个整数表示总花费的最小值。
样例数据
样例输入
5 3
aabaa
ababa
样例输出
3
样例解释
所有子串为:A={aab,aba,baa},B={aba,bab,aba}。可以看出有一对 aba 是相同的,另外要把 aab 改成 aba(花费 2),baa 改成 bab(花费 1),总花费为 3。
子任务
对于所有数据,1≤k≤n≤1.5×105。
- 对于 10% 的数据,n≤11;
- 对于另外 20% 的数据,n≤200;
- 对于另外 20% 的数据,n≤2000;
- 对于另外 10% 的数据,字符串的每一位在小写字母中均匀随机;
- 对于余下 40% 的数据,无特殊限制。