[ARC132D] Between Two Binary Strings

设一个 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$。

[problemUrl]: https://atcoder.jp/contests/arc132/tasks/arc132_d 文字列の **美しさ** を、その文字列のなかで同じ $ 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 $ の間にある文字列の美しさの最大値を出力せよ。

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 $ です。