Problem Description

In the IOI country, a new railway has recently been laid. The trains running on the IOI railway consist of several linked carriages, which can be of two types: I or O. Carriages can only be linked to carriages of different types. Due to the need for a driver's cab, both ends of the train must be of type I. A train is represented by a string of characters that denote the types of its carriages in order, and the length of the train is the length of this string. For example, linking carriages in the order IOIOI forms a train of length 5, and a single carriage I forms a train of length 1. Arranging carriages in the order OIOI or IOOI does not form a valid train.

Several carriages are stored in two depots. Each depot contains carriages arranged in a single row. When forming a train, carriages are taken from the depots and linked together in front of the depots. Only the carriage closest to the entrance of each depot can be taken out, but the order in which carriages are taken from either depot is free.

Before forming a train, any number of carriages can be taken out from the depots and moved to a waiting rail. Once moved to the waiting rail, these carriages cannot be used for forming the train. Once the train formation starts, no more carriages can be moved from the depots to the waiting rail until the formation is complete.

It is not necessary to use all the carriages in the depots when forming a train. That is, it is acceptable to have unused carriages left in the depots after the train formation is complete.

Since it is believed that there will be a very large number of passengers on the railway, the IOI country wants to form the longest possible train.

Input Format

Read the following data from standard input:

• The first line contains two integers, $M$ and $N$, separated by a space.
• The second line contains a string $S$.
• The third line contains a string $T$.

Output Format

Output to standard output a single integer representing the maximum length of the train that can be formed. If no train can be formed, output $0$.

Sample Input and Output

Sample Input #1

5 5
OIOOI
OOIOI

Sample Output #1

7

Sample Input #2

5 9
IIIII
IIIIIIIII

Sample Output #2

1

Notes/Hints

Task

Given the information about the carriages stored in the depots, create a program to find the maximum length of the train that can be formed. Each depot's carriages are represented by a string consisting only of the characters I and O, where each character represents a carriage of the corresponding type. The information for the two depots is given as strings $S$ of length $M$ and $T$ of length $N$, respectively. The first character of each string represents the carriage closest to the depot entrance, and the last character represents the carriage at the back of the depot.

Constraints

• $1 \leq M \leq 2000$ (length of string $S$)
• $1 \leq N \leq 2000$ (length of string $T$)

Grading Criteria

• For 20% of the test cases, $M \leq 10$ and $N \leq 10$.
• For 50% of the test cases, $M \leq 50$ and $N \leq 50$.

见题面 Input 部分

见题面 Output 部分