题目描述

我们将一个字符串的美丽度定义为该字符串中相邻且相同的 $2$ 个字符的位置数。例如，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$ 的距离 $d(s_1, s_2)$ 为：将字符串 $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$ 之间的字符串的美丽度的最大值。

输入格式

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

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

输出格式

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

样例 1

输入

2 3
10110
01101

输出

2

样例 2

输入

4 2
000011
110000

输出

4

样例 3

输入

12 26
01110111101110111101001101111010110110
10011110111011011001111011111101001110

输出

22

说明/提示

限制条件

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

样例解释 1

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

样例解释 2

000011 和 110000 的距离为 $8$。美丽度最大的字符串是 000011 和 110000，答案为 $4$。

由 ChatGPT 4.1 翻译