题目描述

文字列の 美しさ を、その文字列のなかで同じ $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)$ を 「隣り合った $2$ 文字を入れ替える操作によって文字列 $s_1$ を文字列 $s_2$ に並び替えるのに必要な最小の操作回数」 と定義します。

また、$s_1,s_2,s_3\in\ S_{n,m}$ について、$s_2$ が $s_1$ と $s_3$ の 間にある ことを、$d(s_1,s_3)=d(s_1,s_2)+d(s_2,s_3)$ で定義します。

$s,t\in\ S_{n,m}$ が与えられるので、$s$ と $t$ の間にある文字列の美しさの最大値を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$s$ と $t$ の間にある文字列の美しさの最大値を出力せよ。

题目大意

设一个 01 串的美丽值为相同的相邻数字个数。举个例子，00011 的美丽值为 3，而 10101 的美丽值为 0。

设两个长度相同，且 0 的个数相同的 01 串 $s_1,s_2$ 之间的距离 $dis(s_1,s_2)$ 为仅能交换相邻字符，使得 $s_1$ 变成 $s_2$ 的最小交换次数。

如果一个字符串 $s_3$ 满足它在 $s_1,s_2$ 中间，则需要 $dis(s_1,s_2)=dis(s_1,s_3)+dis(s_3,s_2)$。

现在，给定两个长度为 $n+m$ 的，有 $n$ 个 0 的字符串 $s,t$，请求出所有 $s,t$ 中间的字符串中，最大的美丽值。

$2\le n+m\le 3\times 10^5$。

2 3
10110
01101

2

4 2
000011
110000

4

12 26
01110111101110111101001101111010110110
10011110111011011001111011111101001110

22

提示

制約

• $2\ \le\ n\ +\ m\le\ 3\times\ 10^5$
• $0\ \le\ n,m$
• $s,t$ は $n$ 文字の 0 と $m$ 文字の 1 からなる長さ $n+m$ の文字列

Sample Explanation 1

10110 と 01101 の距離は $2$ で、これらの間にある文字列は、10110, 01110, 01101, 10101 です。 それぞれの美しさは $1,2,1,0$ であるため、答えは $2$ です。

Sample Explanation 2

000011 と 110000 の距離は $8$ です。 美しさが最大になる文字列は 000011 と 110000 で、答えは $4$ です。