B. Орехус и строки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Орехус написал $$$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$$$).

Вторая строка содержит строку $$$s$$$ ($$$|s| = n$$$) — строка, из букв «a» и «b».

Третья строка содержит строку $$$t$$$ ($$$|t| = n$$$) — строка, из букв «a» и «b».

Гарантируется, что строка $$$s$$$ лексикографически не больше $$$t$$$.

Выходные данные

Выведите одно число — максимально возможное $$$c$$$.

Примеры
Входные данные
2 4
aa
bb
Выходные данные
6
Входные данные
3 3
aba
bba
Выходные данные
8
Входные данные
4 5
abbb
baaa
Выходные данные
8
Примечание

В первом примере Орехус мог записать строки «aa», «ab», «ba», «bb». Тогда эти $$$4$$$ строки являются префиксами одной из записанных, а кроме них ещё строки «a» и «b». Всего $$$6$$$ строк.

Во втором примере Орехус мог записать строки «aba», «baa», «bba».

В третьем примере есть всего две различные строки, которые мог записать Орехус. Если обе из них написаны, $$$c=8$$$.