最近,Fair Nut 编写了 $$$k$$$ 长度为 $$$n$$$ 的字符串,由字母“a”和“b”组成。他计算了 $$$c$$$ — 作为至少一个书面字符串的前缀的字符串数量。每个字符串只计算一次。
然后,他用绳子弄丢了床单。他记得所有书面字符串按字典顺序不小于字符串 $$$s$$$ 并且不大于字符串 $$$t$$$。他感兴趣的是:他能得到的 $$$c$$$ 的最大值是多少。
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$, $$$1 \leq k \leq 10^9$$$)。
第二行包含一个字符串 $$$s$$$ ($$$|s| = n$$$) — 由字母“a”和“b”组成的字符串。
第三行包含一个字符串 $$$t$$$ ($$$|t| = n$$$) — 由字母“a”和“b”组成的字符串。
保证字符串 $$$s$$$ 按字典顺序不大于 $$$t$$$。
输出
打印一个数字 — $$$c$$$ 的最大值。
示例
输入 #1
2 4 aa bb
输出 #1
6
输入 #2
3 3 aba bba
输出 #2
8
输入 #3
4 5 abbb baaa
输出 #3
8
注意
在第一个示例中,Nut 可以写入字符串“aa”、“ab”、“ba”、“bb”。这些 $$$4$$$ 字符串是至少一个写入字符串的前缀,以及“a”和“b”。总共 $$$6$$$ 字符串。
在第二个示例中,Nut 可以写入字符串“aba”、“baa”、“bba”。
在第三个示例中,Nut 只能写入两个不同的字符串。如果两者都写,$$$c=8$$$。