002 - IOI列車で行こう

問題

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

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

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

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

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

図: 列車を編成している途中であり，このとき車庫にある車両を待機用レールに移すことはできない．
この図は入出力例 1 に対応している．

課題

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

制限

1 ≤ M ≤ 2,000 文字列 S の長さ
1 ≤ N ≤ 2,000 文字列 T の長さ

入力

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

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

出力

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

採点基準

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

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

入出力例

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 を出力する．

5 9
IIIII
IIIIIIIII

1

1 つの車両のみからなる列車 I も列車としての条件を満たすことに注意せよ．