题目描述

让我们定义字符串的美丽度为相邻字符相同的位置数量。例如，00011 的美丽度是 $3$，而 10101 的美丽度是 $0$。

设 $S_{n,m}$ 为由 $n$ 个 0 和 $m$ 个 1 组成的长度为 $n+m$ 的所有字符串的集合。

对于 $s_1,s_2 \\in S_{n,m}$，将字符串 $s_1$ 调整为 $s_2$ 所需的最小交换次数定义为 $s_1$ 和 $s_2$ 之间的距离，记作 $d(s_1,s_2)$。

此外，对于 $s_1,s_2,s_3\\in S_{n,m}$，当 $d(s_1,s_3)=d(s_1,s_2)+d(s_2,s_3)$ 时，称 $s_2$ 位于 $s_1$ 和 $s_3$ 之间。

给定 $s,t\\in S_{n,m}$，计算 $s$ 和 $t$ 之间的字符串的最大美丽度。

约束条件

• $2 \\le n + m\\le 3\\times 10^5$
• $0 \\le n,m$
• $s$ 和 $t$ 都是由 $n$ 个 0 和 $m$ 个 1 组成的长度为 $n+m$ 的字符串。

输入

从标准输入中以以下格式给出输入：

$n$ $m$ $s$ $t$

输出

输出 $s$ 和 $t$ 之间字符串的最大美丽度。

示例输入1

2 3
10110
01101

示例输出1

2

在 10110 和 01101 之间的距离为 $2$ 的字符串有：10110, 01110, 01101, 10101。它们的美丽度分别为 $1$，$2$，$1$，$0$，因此答案为 $2$。

示例输入2

4 2
000011
110000

示例输出2

4

在 000011 和 110000 之间的距离为 $8$ 的字符串中，美丽度最大的是 000011 和 110000，因此答案为 $4$。

示例输入3

12 26
01110111101110111101001101111010110110
10011110111011011001111011111101001110

示例输出3

22