The Fair Nut and Strings
Contest: Codeforces Round 526 (Div. 1)
Difficulty rating: 2000
Tags: greedy, 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$$$.

Input format:
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$$$.

Output format:
Print one number — maximal value of $$$c$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
2 4
aa
bb

Example output:
6

Example input:
3 3
aba
bba

Example output:
8

Editorial:
If $$$s$$$ and $$$t$$$ are equal, answer is $$$n$$$.
Let's cut common prefix of $$$s$$$ and $$$t$$$, and increase answer to its length. Now $$$s$$$ starts from "a" and $$$t$$$ starts from "b". Let $$$m$$$ is new lengths of $$$s$$$ and $$$t$$$. If string $$$s$$$ weren't written, we can change the lexicographically smallest string to $$$s$$$, and $$$c$$$ will not decrease. We can do the same thing with $$$t$$$. Now $$$s$$$ and $$$t$$$ are in answer. We can increase answer by $$$2 \cdot m$$$, decrease $$$k$$$ by 2 and don't count strings, which are prefixes of $$$s$$$ and $$$t$$$, while calculating $$$c$$$. Let's divide strings in answer into groups — two strings are in one group if and only if their first characters are equal and their largest common prefixes with $$$s$$$ or $$$t$$$ (it depends on the first character) are equal. Let length of group be $$$m - lcp$$$, where $$$lcp$$$ — length of this common prefix.
$$$c$$$ is equal to the number of vertexes in trie on written strings. If we have fixed $$$l$$$ — number of strings, which will belong to some group, we have to maximize size of set of vertexes, which is union of $$$l$$$ ways in full binary tree with height $$$h$$$, equals to length of group. It can be proved by induction, that the first way increases size of set by $$$h$$$, the second by $$$h - 1$$$, next 2 ways by $$$h - 2$$$, next 4 ways by $$$h - 3$$$, etc. We can create array $$$p$$$, where $$$p_{i}$$$ - how many ways increase answer by $$$h - i$$$. Note that these values are additive - if we have two independent binary trees and want to distribute some number of ways between them, we can sum their arrays (and it is how prove the previous fact).
We have $$$O(n)$$$ independent groups, and we want to sum their arrays fast. Every binary tree increases values on suffix by $$$[1, 1, 2, 4, ...]$$$. Let's forget about the first $$$1$$$ and add it in the end. Then, put $$$1$$$ to the second position in suffix, and add $$$2 \cdot a_{i}$$$ to $$$a_{i + 1}$$$ for $$$1 \le i \le n - 1$$$ in increasing order, where $$$a$$$ — array, which we want to get. Note that values in this array could be very big, but if we change values, bigger than $$$k$$$, to $$$k$$$, answer will not change (because there are only $$$k$$$ ways).
To calculate answer, let's take the prefix with sum $$$k$$$ (if there are no such prefix, we take the first prefix with sum, which is bigger than $$$k$$$ and decrease last element), fill other elements with $$$0$$$. Answer will be equal sum $$$a[i] \cdot i$$$ for $$$1 \le i \le m$$$.