달려라 IOI 열차

IOI 국가는 최근 새로운 열차 노선인 IOI선을 개통했다.

IOI 열차는 한 칸짜리 단위 열차 여러 대가 연결된 모습을 하고 있으며 단위 열차의 종류는 I 또는 O이다.

안전을 위해 IOI 열차의 인접한 칸은 서로 다른 종류여야 하며, 운전석은 I칸에만 있기 때문에 열차의 양 끝 칸은 항상 I여야 한다.

예를 들어 OIOI나 IOOI와 같은 열차는 불가능하다.

열차는 각 차량의 종류를 나타낸 문자를 순서대로 이어 붙인 문자열로 나타낼 수 있으며 문자열의 길이가 곧 열차의 길이이다.

예를 들어 열차 IOIOI의 길이는 5이며 열차 I는 길이 1의 열차가 된다.

이제 IOI선의 개통 전날이다.

역사적인 첫 운행을 맡게 된 차장 승택이는 가능한 한 많은 승객을 태울 수 있도록 현재 보관 중인 단위 열차들을 이어 붙여 한 대의 긴 IOI 열차를 만들려고 한다.

현재 단위 열차 I 또는 O 여러 대가 두 차고지에 일렬로 주차되어 있다.

두 차고지 중 어디서 열차를 꺼낼 지는 자유지만, 열차를 들어서 옮길 수는 없기 때문에 차고의 입구에 가까운 열차부터 차례차례 꺼낼 수밖에 없다.

단, 열차 편성이 시작되기 전에 각 차고지에서 원하는 만큼씩 열차를 미리 외부 차고로 보내둘 수가 있다.

한 번 외부 차고로 보낸 열차칸은 열차를 편성할 때 사용할 수 없다.

또한 한 번 열차 편성이 시작된 다음엔 외부 차고로 열차를 보낼 수 없다.

위는 예제 입력에 대응하는 그림이다. 열차 편성이 시작되면 더 이상 외부 차고를 이용할 수가 없으며,

외부 차고의 열차는 열차 편성에 이용할 수가 없다.

승택이는 적절히 차량 대기소로 열차를 보낸 뒤 규칙에 맞게 열차를 이어붙여 한 대의 긴 IOI 열차를 만들 것이다.

이때 얼마나 긴 열차를 만들 수 있을까?

첫 줄에 차고 S에 저장된 열차의 수 N, 차고 T에 주차된 열차의 수 M이 주어진다. (1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000)

두 번째 줄에 차고 S에 저장된 열차들이 문자열 한 줄로 주어진다.

세 번째 줄에 차고 T에 저장된 열차들이 문자열 한 줄로 주어진다.

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

첫 줄에 가장 긴 열차의 길이를 출력한다.

열차를 만들 수 없다면 0을 출력한다.