달려라 IOI 열차

IOI 국가가 새로운 노선 IOI선을 개통했다.

IOI 열차는 한 칸짜리 단위 차량 여러 대를 한 줄로 이어 붙인 것이며, 각 단위 차량의 종류는 I 또는 O 두 가지뿐이다.

안전 규칙상 인접한 두 칸은 종류가 서로 달라야 하고, 운전석이 I칸에만 있으므로 열차의 양 끝 칸은 반드시 I여야 한다. 따라서 올바른 열차는 I로 시작해 I로 끝나면서 I와 O가 번갈아 나오는 형태(예: I, IOI, IOIOI, ...)이고, 길이는 항상 홀수이다. 예를 들어 OIOI나 IOOI는 올바른 열차가 아니다.

열차는 앞에서부터 각 칸의 종류를 이어 붙인 문자열로 나타내며, 문자열의 길이가 곧 열차의 길이이다. 예를 들어 IOIOI의 길이는 5이고, I는 길이 1의 열차이다.

지금 단위 차량들은 두 차고 S와 T에 각각 한 줄로 주차되어 있다. 각 차고에서는 들어서 옮길 수 없어, 입구에 가장 가까운(맨 앞) 차량부터 순서대로만 꺼낼 수 있다.

편성을 시작하기 전에는, 각 차고에서 앞쪽 차량을 원하는 개수만큼 미리 외부 차고로 빼둘 수 있다(즉 각 차고의 접두부를 원하는 만큼 버릴 수 있다). 외부로 보낸 차량은 편성에 쓸 수 없다. 편성이 한 번 시작되면 더 이상 외부로 차량을 보낼 수 없으므로, 그 뒤로는 차고에서 꺼낸 차량을 반드시 열차 끝에 이어 붙여야 한다.

편성이 시작되면, 두 차고 중 한 곳의 맨 앞 차량을 꺼내 지금까지 만든 열차의 끝에 이어 붙이는 일을 원하는 만큼 반복하고, 원할 때 멈춘다. 이렇게 만든 열차가 올바른 IOI 열차가 되도록 할 때, 만들 수 있는 열차의 최대 길이를 구하라.

첫 줄에 차고 S에 주차된 차량의 수 N과 차고 T에 주차된 차량의 수 M이 주어진다. ($1 \le N, M \le 2000$)

둘째 줄에 차고 S의 차량들을 나타내는 길이 N의 문자열이 주어진다.

셋째 줄에 차고 T의 차량들을 나타내는 길이 M의 문자열이 주어진다.

각 문자열의 첫 글자가 해당 차고의 입구 쪽에 주차된 차량이다.

만들 수 있는 올바른 IOI 열차의 최대 길이를 한 줄에 출력한다.

어떤 열차도 만들 수 없으면 0을 출력한다.