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

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 ≤ 2000      文字列 S の長さ
• 1 ≤ N ≤ 2000      文字列 T の長さ

入力

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

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

出力

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

入出力例

入力例 1

5 5
OIOOI
OOIOI

出力例 1

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

入力例 2

5 9
IIIII
IIIIIIIII

出力例 2

1

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

---