문제 설명
IOI 왕국에서는 이번에 새로 철도를 부설했다. IOI 왕국의 철도를 달리는 열차는 몇 개의 차량이 연결된 것이며, 차량에는 I, O의 $2$종류가 있다. 차량은 각각 서로 다른 종류의 차량하고만 연결할 수 있다. 또한 열차에 운전석을 설치해야 하므로, 열차의 양 끝 차량은 종류 I여야만 한다. 열차는 차량의 종류를 나타내는 문자를 순서대로 이어 붙인 문자열로 표현되며, 열차의 길이는 그 문자열의 길이라고 한다. 예를 들어 IOIOI의 순서로 차량을 연결하면 길이 $5$인 열차를 편성할 수 있고, 차량 I는 단독으로 길이 $1$인 열차이다. 차량을 OIOI나 IOOI 같은 순서로 나열해서는 열차를 편성할 수 없다.
몇 개의 차량이 $2$개의 차고에 격납되어 있다. 각 차고 안에는 차량이 일렬로 나열되어 있다. 열차를 편성할 때는 차고에서 차량을 꺼내어 차고 앞에서 연결해 나간다. 차고에서 꺼낼 수 있는 차량은 차고 입구에 가장 가까운 차량뿐이지만, 어느 쪽 차고에서 차량을 꺼낼지의 순서는 자유이다.
열차를 편성하기 전에, 차량을 원하는 만큼 차고에서 꺼내어 별도의 대기용 레일로 옮길 수 있다. 한 번 대기용 레일로 옮긴 차량은 이후 열차를 편성하는 데 사용할 수 없다. 또한 한 번 열차 편성을 시작하면 그 편성이 끝날 때까지는 차량을 차고에서 대기용 레일로 옮길 수 없다.
열차를 편성할 때 차고 안의 모든 차량을 다 써야 할 필요는 없다. 즉, 열차 편성을 마친 뒤 차고 안에 사용되지 않은 차량이 남아 있어도 상관없다.
IOI 왕국에서는 철도를 타는 사람이 매우 많을 것으로 예상되므로, 가능한 한 긴 열차를 편성하고 싶다.
그림: 열차를 편성하는 도중이며(위: 대기용 레일, 왼쪽 아래: 편성 중인 열차, 오른쪽: 차고 S와 차고 T), 이때 차고에 있는 차량을 대기용 레일로 옮길 수는 없다. 이 그림은 입출력 예제 1에 대응한다.
과제
차고에 격납된 차량의 정보가 주어졌을 때, 편성할 수 있는 열차의 길이의 최댓값을 구하는 프로그램을 작성하라. 각 차고에 격납된 차량의 열은 $2$종류의 문자 I, O만으로 이루어진 문자열로 표현되며, $2$개의 차고의 정보는 각각 길이 $M$인 문자열 $S$ 및 길이 $N$인 문자열 $T$로 주어진다. 각 문자가 $1$개의 차량을 나타내며, 그 문자는 차량의 종류와 같다. 문자열의 $1$번째 문자는 차고 입구에 가장 가까운 차량을 나타내고, 마지막 문자는 차고의 가장 안쪽에 있는 차량을 나타낸다.
제한
- $1 \le M \le 2\,000$: 문자열 $S$의 길이.
- $1 \le N \le 2\,000$: 문자열 $T$의 길이.
입력
표준 입력에서 다음 데이터를 읽어들여라.
- $1$번째 줄에는 $M, N$이 공백으로 구분되어 적혀 있다.
- $2$번째 줄에는 문자열 $S$가 적혀 있다.
- $3$번째 줄에는 문자열 $T$가 적혀 있다.
출력
표준 출력에, 편성할 수 있는 열차의 길이의 최댓값을 나타내는 정수를 $1$줄로 출력하라. 열차를 $1$개도 편성할 수 없는 경우에는 0을 출력하라.
채점 기준
- 채점용 데이터 중 배점의 $20\%$에 대해서는 $M \le 10$, $N \le 10$을 만족한다.
- 채점용 데이터 중 배점의 $50\%$에 대해서는 $M \le 50$, $N \le 50$을 만족한다.
입출력 예제 1
5 5 OIOOI OOIOI
7
$S$로 표현되는 차고를 차고 S라 하고, $T$로 표현되는 차고를 차고 T라 하자. 이때 예를 들어 차고 S에서 처음 $1$개 차량, 차고 T에서 처음 $2$개 차량을 꺼내어 대기시킨 후, 차고 S, 차고 S, 차고 T, 차고 S, 차고 S, 차고 T, 차고 T의 순서로 차량을 꺼내면 길이 $7$인 열차 IOIOIOI를 편성할 수 있다.
그 밖에도 차고 S에서 처음 $1$개 차량, 차고 T에서 처음 $2$개 차량을 꺼내어 대기시킨 후, 차고 T, 차고 T, 차고 S, 차고 S, 차고 T, 차고 S, 차고 S의 순서로 차량을 꺼내는 것으로도 길이 $7$인 열차를 편성할 수 있다. 이보다 긴 열차를 편성할 수는 없으므로 $7$을 출력한다.
입출력 예제 2
5 9 IIIII IIIIIIIII
1
$1$개의 차량만으로 이루어진 열차 I도 열차로서의 조건을 만족함에 주의하라.