IOI 列車で行こう (Take the 'IOI' train)

IOI 国ではこのたび新たに鉄道を敷設した．IOI 国の鉄道を走る列車はいくつかの車両が連結されたものであり，車両には I，O の \(2\) 種類がある．車両はそれぞれ異なる種類の車両としか連結できない．また，列車に運転席を設ける関係上，列車の両端の車両は種類 I でなければならない．列車は車両の種類を表す文字を順につなげた文字列で表され，列車の長さはその文字列の長さであるとする．たとえば， IOIOI の順に車両を連結すると長さ \(5\) の列車を編成でき，また車両 I は単独で長さ \(1\) の列車である．車両を OIOI や IOOI といった順に並べても列車を編成することはできない．

いくつかの車両が \(2\) つの車庫に格納されている．それぞれの車庫の中には車両が一列に並んでいる．列車を編成するときは車庫から車両を出してきて車庫前で連結していく．車庫から出せる車両は最も車庫の入り口に近い車両のみであるが，どちらの車庫から車両を出すかの順番については自由である．

列車を編成する前に，車両を好きなだけ車庫から出して別の待機用レールに移すことができる．一度待機用レールに移した車両は今後列車を編成するために使うことはできない．また，一度列車の編成を始めるとその編成が終わるまでの間は車両を車庫から待機用レールに移すことはできない．

列車を編成するとき，車庫内の全ての車両を使い切る必要はない．すなわち，列車の編成を終えた後，車庫内に使われなかった車両が残っていても構わない．

IOI 国では鉄道に乗る人がとてもたくさんいると考えられているので，できるだけ長い列車を編成したい．

課題

車庫に格納された車両の情報が与えられたとき，編成できる列車の長さの最大値を求めるプログラムを作成せよ．それぞれの車庫に格納された車両の列は \(2\) 種類の文字 I，O のみからなる文字列で表され，\(2\) つの車庫の情報はそれぞれ長さ \(M\) の文字列 \(S\) および長さ \(N\) の文字列 \(T\) として与えられる．各文字が \(1\) つの車両を表し，その文字は車両の種類と同じである．文字列の \(1\) 文字目は最も車庫の入り口に近い車両を表し，末尾の文字が車庫の最も奥にある車両を表す．

標準入力から以下のデータを読み込め．

• \(1\) 行目には \(M, N\) が空白区切りで書かれている．
• \(2\) 行目には文字列 \(S\) が書かれている．
• \(3\) 行目には文字列 \(T\) が書かれている．

標準出力に，編成できる列車の長さの最大値を表す整数を \(1\) 行で出力せよ． 列車が \(1\) つも編成できない場合は，\(0\) を出力せよ．

採点用データのうち，配点の \(20\) %分については，\(M \leqq 10\)，\(N \leqq 10\) を満たす．

採点用データのうち，配点の \(50\) %分については，\(M \leqq 50\)，\(N \leqq 50\) を満たす．

JOI 2013 · JCIOI · CC BY-SA 4.0