← 返回题目列表

Codeforces · 1083/B

B. 公平的坚果和琴弦

中文机器翻译题面 查看原题

最近,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$$$。