Problem Statement

In the Kingdom of IOI, a railway has recently been newly constructed. A train running on the railway of the Kingdom of IOI consists of several cars coupled together, and there are $2$ types of cars: I and O. A car can only be coupled with a car of a different type. Furthermore, because driver cabs must be installed at both ends of a train, the cars at both ends of a train must be of type I. A train is represented by a string formed by concatenating the characters representing the types of its cars in order, and the length of the train is defined to be the length of that string. For example, coupling cars in the order IOIOI forms a train of length $5$, and a single car I by itself is a train of length $1$. One cannot form a train by arranging cars in an order such as OIOI or IOOI.

Several cars are stored in $2$ depots. Inside each depot, the cars are lined up in a single row. When forming a train, cars are taken out from the depots and coupled together in front of the depots. The only car that can be taken out from a depot is the one closest to the entrance of that depot, but the order in which cars are taken out from Either of the two depots can be chosen freely.

Before starting to form a train, any number of cars can be taken out from the depots and moved to a separate waiting rail. Cars moved to the waiting rail cannot be used to form the train thereafter. Also, once the formation of the train has begun, no cars can be moved from the depots to the waiting rail until the formation is finished.

When forming a train, it is not necessary to use up all the cars in the depots. That is, after finishing the formation of the train, unused cars may remain inside the depots.

Since it is expected that very many people will ride the railway in the Kingdom of IOI, we want to form a train that is as long as possible.

Figure: In the middle of forming a train (top: waiting rail; bottom-left: train being formed; right: depot S and depot T); at this point, cars in the depots cannot be moved to the waiting rail. This figure corresponds to Sample 1.

Task

Given information about the cars stored in the depots, write a program to find the maximum possible length of a train that can be formed. The sequence of cars stored in each depot is represented by a string consisting only of the $2$ types of characters I and O, and the information of the $2$ depots is given as a string $S$ of length $M$ and a string $T$ of length $N$, respectively. Each character represents $1$ car, and the character is the same as the type of the car. The $1$-st character of the string represents the car closest to the entrance of the depot, and the last character represents the car furthest back in the depot.

Constraints

• $1 \le M \le 2\,000$: the length of string $S$.
• $1 \le N \le 2\,000$: the length of string $T$.

Input

Read the following data from standard input.

• On the $1$-st line, $M, N$ are written separated by a space.
• On the $2$-nd line, the string $S$ is written.
• On the $3$-rd line, the string $T$ is written.

Output

Output on $1$ line to standard output the integer representing the maximum possible length of a train that can be formed. If not even $1$ train can be formed, output 0.

Grading

• For $20\%$ of the total score, $M \le 10$ and $N \le 10$ hold.
• For $50\%$ of the total score, $M \le 50$ and $N \le 50$ hold.

Sample 1

5 5
OIOOI
OOIOI

7

Let the depot represented by $S$ be depot S, and let the depot represented by $T$ be depot T. Then, for example, after taking out the first $1$ car from depot S and the first $2$ cars from depot T and moving them to the waiting rail, if we take out cars in the order: depot S, depot S, depot T, depot S, depot S, depot T, depot T, we can form the train IOIOIOI of length $7$.

Alternatively, after taking out the first $1$ car from depot S and the first $2$ cars from depot T and moving them to the waiting rail, we can also form a train of length $7$ by taking out cars in the order: depot T, depot T, depot S, depot S, depot T, depot S, depot S. Since it is impossible to form a longer train than this, output $7$.

Sample 2

5 9
IIIII
IIIIIIIII

1

Note that the train I consisting of only $1$ car also satisfies the conditions for a train.