{"raw_statement":[{"iden":"problem statement","content":"Let us define the **beauty** of the string as the number of positions where two adjacent characters are the same. For example, the beauty of `00011` is $3$, and the beauty of `10101` is $0$.\nLet $S_{n,m}$ be the set of all strings of length $n+m$ formed of $n$ `0`s and $m$ `1`s.\nFor $s_1,s_2 \\in S_{n,m}$, let us define the **distance** of $s_1$ and $s_2$, $d(s_1,s_2)$, as the minimum number of swaps needed when rearranging the string $s_1$ to $s_2$ by swaps of two adjacent characters.\nAdditionally, for $s_1,s_2,s_3\\in S_{n,m}$, $s_2$ is said to be **between** $s_1$ and $s_3$ when $d(s_1,s_3)=d(s_1,s_2)+d(s_2,s_3)$.\nGiven $s,t\\in S_{n,m}$, print the greatest beauty of a string between $s$ and $t$."},{"iden":"constraints","content":"*   $2 \\le n + m\\le 3\\times 10^5$\n*   $0 \\le n,m$\n*   Each of $s$ and $t$ is a string of length $n+m$ formed of $n$ `0`s and $m$ `1`s."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$n$ $m$\n$s$\n$t$"},{"iden":"sample input 1","content":"2 3\n10110\n01101"},{"iden":"sample output 1","content":"2\n\nBetween `10110` and `01101`, whose distance is $2$, we have the following strings: `10110`, `01110`, `01101`, `10101`. Their beauties are $1$, $2$, $1$, $0$, respectively, so the answer is $2$."},{"iden":"sample input 2","content":"4 2\n000011\n110000"},{"iden":"sample output 2","content":"4\n\nBetween `000011` and `110000`, whose distance is $8$, the strings with the greatest beauty are `000011` and `110000`, so the answer is $4$."},{"iden":"sample input 3","content":"12 26\n01110111101110111101001101111010110110\n10011110111011011001111011111101001110"},{"iden":"sample output 3","content":"22"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}