Problem Statement

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.
Let S_{n,m} be the set of all strings of length n+m formed of n 0s and m 1s.
For $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.
Additionally, 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).
Given $s,t\in$ S_{n,m}, print the greatest beauty of a string between s and t.

Input

Input is given from Standard Input in the following format:
n m
s
t

Output

Print the greatest beauty of a string between s and t.

Constraints

• $2 \le n + m\le 3\times 10^5$
• $0 \le n,m$
• Each of s and t is a string of length n+m formed of n 0s and m 1s.

Sample Input 1

2 3
10110
01101

Sample Output 1

2

Between 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.

Sample Input 2

4 2
000011
110000

Sample Output 2

4

Between 000011 and 110000, whose distance is 8, the strings with the greatest beauty are 000011 and 110000, so the answer is 4.

Sample Input 3

12 26
01110111101110111101001101111010110110
10011110111011011001111011111101001110

Sample Output 3

22

见题面 Input 部分

见题面 Output 部分