#P1083B. The Fair Nut and Strings
-
ID: 4921
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 7
Uploaded By:
Hydro
Tags> The Fair Nut and Strings
Description
Recently, the Fair Nut has written strings of length , consisting of letters "a" and "b". He calculated — 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 and not bigger than string . He is interested: what is the maximum value of that he could get.
A string is lexicographically smaller than a string if and only if one of the following holds:
- is a prefix of , but ;
- in the first position where and differ, the string has a letter that appears earlier in the alphabet than the corresponding letter in .
The first line contains two integers and (, ).
The second line contains a string () — the string consisting of letters "a" and "b.
The third line contains a string () — the string consisting of letters "a" and "b.
It is guaranteed that string is lexicographically not bigger than .
Print one number — maximal value of .
Input
The first line contains two integers and (, ).
The second line contains a string () — the string consisting of letters "a" and "b.
The third line contains a string () — the string consisting of letters "a" and "b.
It is guaranteed that string is lexicographically not bigger than .
Output
Print one number — maximal value of .
Note
In the first example, Nut could write strings "aa", "ab", "ba", "bb". These strings are prefixes of at least one of the written strings, as well as "a" and "b". Totally, 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, .