문제번역 : 경남과학고 29기 도회린

IOI나라에서는 새로운 철도를 만들었다. IOI나라의 철도에 운행하는 열차는 몇몇의 차량이 연결된 것이고, 차량의 종류에는 I, O의 두 종류가 있다. 차량은 서로 다른 종류의 차량끼리만 연결할 수 있다. 또한 열차 운전석을 마련하기 위해서, 양쪽 끝 차량은 ‘I’ 차량으로 해야한다. 열차는 차량의 종류를 나타내는 글자를 차례로 연결한 문자열로 표시되며, 열차의 길이는 문자열의 길이와 같다. 예를 들어 IOIOI의 순서로 차량을 연결하면 길이가 5인 열차를 편성한 것이며, 차량 I가 단독으로 존재한다면 이는 길이가 1인 열차이다. 차량을 OIOI, IOOI와 같은 순서로 나열하면 열차를 편성할 수 없다.

일부 차량이 2개의 주차장에 서있다. 각 주차장에는 차량이 한 줄로 줄지어있다. 열차를 구성할 때, 주차장에서 차량을 내오고 주차장 앞에서 연결해간다. 주차장에서 꺼낼 수 있는 차량은 가장 주차장 입구에서 가까운 차량뿐이지만, 2개의 주차장 중에서 어느 주차장에서 차량을 내올 것인지는 자유롭게 선택할 수 있다.

열차를 편성하기 전에, 차량을 원하는 만큼 주차장에서 다른 대기 레일로 가져올 수 있다. 하지만 대기 레일에 옮긴 차량은 더 이상 열차를 편성하는 데 사용할 수 없다. 또한 한 번 열차 편성을 시작하면, 그 편성이 완료되기 전에는 차량을 주차장에서 대기 레일로 옮길 수 없다.

열차를 편성할 때, 주차장에 있는 모든 차량을 꺼낼 필요는 없다. 즉, 열차의 편성을 마친 뒤 주차장에 사용되지 않은 차량이 남아있어도 무관하다.

 IOI 국가에서는 철도 고객의 수요가 매우 많다고 판단하여, 가능한 가장 길게 열차를 편성하고 싶다. 주차장에 저장된 차량 정보가 주어졌을 때, 구성할 수 있는 열차의 길이의 최댓값을 구하는 프로그램을 작성하시오. 각 주차장에 저장된 차량의 순서는 문자 I, O로만 이루어진, 길이가 M인 문자열 S와 길이가 N인 문자열 T로 주어진다. 각 문자는 하나의 차량을 나타내며, 그 문자는 차량의 종류와 같다. 문자열의 첫 번째 문자가 가장 주차장 입구에서 가까운 차량이고, 마지막 문자가 가장 안쪽 차량이다.

첫 번째 줄에는 두 정수 M과 N이 주어진다.

두 번째 줄에는 길이가 M인 문자열 S이 주어진다. (1 ≦ M ≦ 2,000)

세 번째 줄에는 길이가 N인 문자열 T이 주어진다. (1 ≦ N ≦ 2,000)

채점 데이터의 20%는 M ≦ 10, N ≦ 10의 범위로 주어진다.

채점 데이터의 50%는 M ≦ 50, N ≦ 50의 범위로 주어진다.

구성할 수 있는 열차 길이의 최댓값을 나타내는 정수를 출력하라. 구성할 수 있는 열차의 경우가 없는 경우에는 0을 출력하라.

차량 I 하나만으로도 열차의 편성 조건을 충족할 수 있음에 주의하라.

「입출력 예시 1」

(<그림>을 참고하라.) 문자열 S에 의해 표현되는 주차장을 주차장 S, 문자열 T에 의해 표현되는 주차장을 주차장 T라고 하자. 이 때 주차장 S에서 차량 하나, 주차장 T에서 처음 두 차량을 꺼내서 대기 레일로 옮기고, 주차장 S, 주차장 S, 주차장 T, 주차장 S, 주차장 S, 주차장 T, 주차장 T의 순서에 따라 차량을 꺼내면 길이가 7인 열차 IOIOIOI를 편성할 수 있다. 혹은 주차장 S에서 차량 하나, 주차장 T에서 처음 두 차량을 꺼내서 대기 레일로 옮기고, 주차장 T, 주차장 T, 주차장 S, 주차장 S, 주차장 T, 주차장 S, 주차장 S의 순서로 차량을 꺼내서 열차를 편성해도 길이가 7이다. 이것보다 더 길게 열차를 편성할 수 없기 때문에, 7이 출력된다.

JOI 2012/2013 본선