Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. The Fair Nut and Strings

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputRecently, 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

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

Print one number — maximal value of $$$c$$$.

Examples

Input

2 4 aa bb

Output

6

Input

3 3 aba bba

Output

8

Input

4 5 abbb baaa

Output

8

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

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/16/2022 08:10:47 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|