CF1083B The Fair Nut and Strings

最近，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$）。 第二行包含一个长度为 $n$ 的字符串 $s$，该字符串仅由字母 "a" 和 "b" 组成。 第三行包含一个长度为 $n$ 的字符串 $t$，该字符串仅由字母 "a" 和 "b" 组成。 保证字符串 $s$ 的字典序不大于 $t$。

输出一个整数，表示 $c$ 的最大值。

在第一个样例中，Nut 可以写下字符串 "aa"、"ab"、"ba"、"bb"。这 $4$ 个字符串的所有前缀 "a"、"b" 也是至少某个字符串的前缀。总共有 $6$ 个字符串。 在第二个样例中，Nut 可以写下字符串 "aba"、"baa"、"bba"。 在第三个样例中，只能写下两个不同的字符串。如果这两个都写下，则 $c=8$。 由 ChatGPT 4.1 翻译