CF1083B.The Fair Nut and Strings

Recently, the Fair Nut has written $k$ strings of length $n$, consisting of letters "a" and "b". He calculated $c$ — the number of strings that are prefixes of at least one of the written strings. Every string was counted only one time.

Then, he lost his sheet with strings. He remembers that all written strings were lexicographically not smaller than string $s$ and not bigger than string $t$. He is interested: what is the maximum value of $c$ that he could get.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$;
• in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

最近，Fair Nut 写下了 $k$ 个长度为 $n$ 的字符串，每个字符串仅由字母 “a” 和 “b” 组成。他计算了 $c$ —— 即至少是所写字符串中某一个的前缀的字符串的个数（每个字符串仅计数一次）。

随后，他丢失了写有这些字符串的纸张。但他记得所有写下的字符串在字典序上均不小于字符串 $s$，且不大于字符串 $t$。他想知道：他可能得到的最大 $c$ 值是多少？

字符串 $a$ 在字典序上小于字符串 $b$，当且仅当满足以下条件之一：

• $a$ 是 $b$ 的前缀，但 $a \ne b$；
• 在 $a$ 与 $b$ 首次出现不同字符的位置上，$a$ 中的字符在字母表中早于 $b$ 中对应位置的字符。

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 5 \cdot 10^5$, $1 \leq k \leq 10^9$).

The second line contains a string $s$ ($|s| = n$) — the string consisting of letters "a" and "b.

The third line contains a string $t$ ($|t| = n$) — the string consisting of letters "a" and "b.

It is guaranteed that string $s$ is lexicographically not bigger than $t$.

第一行包含两个整数 $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$。

Print one number — maximal value of $c$.

输出一个数字——$c$ 的最大值。

In the first example, Nut could write strings "aa", "ab", "ba", "bb". These $4$ strings are prefixes of at least one of the written strings, as well as "a" and "b". Totally, $6$ strings.

In the second example, Nut could write strings "aba", "baa", "bba".

In the third example, there are only two different strings that Nut could write. If both of them are written, $c=8$.

在第一个例子中，Nut 可以写出字符串 "aa"、"ab"、"ba"、"bb"。这 $4$ 个字符串均是至少一个已写出字符串的前缀，此外 "a" 和 "b" 也是。总计 $6$ 个字符串。

在第二个例子中，Nut 可以写出字符串 "aba"、"baa"、"bba"。

在第三个例子中，Nut 只能写出两个不同的字符串。若这两个字符串均被写出，则 $c=8$。