Nut và những xâu ký tự

Có $k$ xâu, mỗi xâu có độ dài đúng bằng $n$ và chỉ gồm hai chữ cái "a" và "b". Gọi $c$ là số lượng xâu khác nhau mà là tiền tố của ít nhất một trong $k$ xâu đó (mỗi xâu tiền tố chỉ được đếm một lần).

Bạn không biết $k$ xâu cụ thể, chỉ biết rằng mọi xâu đều lớn hơn hoặc bằng xâu $s$ và nhỏ hơn hoặc bằng xâu $t$ theo thứ tự từ điển (với $s$, $t$ cho trước, cùng độ dài $n$, và $s$ không lớn hơn $t$).

Hãy tìm giá trị lớn nhất có thể của $c$.

Một xâu $a$ nhỏ hơn xâu $b$ theo thứ tự từ điển nếu: $a$ là tiền tố thực sự của $b$; hoặc tại vị trí đầu tiên hai xâu khác nhau, chữ cái của $a$ đứng trước chữ cái của $b$ trong bảng chữ cái.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa xâu $s$ độ dài $n$ gồm các chữ "a" và "b".
• Dòng thứ ba chứa xâu $t$ độ dài $n$ gồm các chữ "a" và "b".

Đảm bảo $s$ không lớn hơn $t$ theo thứ tự từ điển.

Dữ liệu ra

• In ra một số nguyên: giá trị lớn nhất có thể của $c$.

Ràng buộc

• $1\le n\le 5·{10}^5$
• $1\le k\le {10}^9$
• $|s|=|t|=n$, các xâu chỉ gồm chữ "a" và "b".

Ví dụ