题目链接

题意

定义一个长度为 $n$ 字符串 $S$ 的美丽值为有多少个 $1\le i <n$ 满足 $S_i=S_{i+1}$。

定义两个由 $n$ 个 $0$，$m$ 个 $1$ 组成的字符串 $S,T$ ，$dis(S,T)$ 表示 $S$ 最少通过多少次交换两个相邻元素使得 $S=T$。

定义一个字符串 $P$ 在 $S$ 与 $T$ 中间，满足 $dis(S,P)+dis(P,T)=dis(S,T)$。

已知两个字符串 $S,T$，求对于所有 $P$ 在 $S,T$ 中间，美丽值的最大值。

输入格式

一行两个数 $n,m$。

接下来两行，每行一个字符串，分别表示 $S,T$。

输出格式

一行一个数，表示答案。

样例

2 3
10110
01101

2

4 2
000011
110000

4

12 26
01110111101110111101001101111010110110
10011110111011011001111011111101001110

22