Deskripsi Masalah

Di Kerajaan IOI, sebuah jalur kereta api baru saja dibangun. Kereta yang berjalan di jalur kereta api Kerajaan IOI terdiri dari beberapa gerbong yang digandengkan, dan terdapat $2$ jenis gerbong: I dan O. Sebuah gerbong hanya dapat digandengkan dengan gerbong dari jenis yang berbeda. Selain itu, karena ruang kemudi harus dipasang di kedua ujung kereta, gerbong di kedua ujung kereta harus berjenis I. Sebuah kereta dinyatakan dengan string yang dibentuk dengan menggabungkan karakter-karakter yang menyatakan jenis gerbongnya secara berurutan, dan panjang kereta didefinisikan sebagai panjang string tersebut. Sebagai contoh, menggandengkan gerbong dengan urutan IOIOI dapat membentuk kereta sepanjang $5$, dan satu gerbong I saja merupakan kereta sepanjang $1$. Kita tidak dapat membentuk kereta dengan menyusun gerbong dalam urutan seperti OIOI atau IOOI.

Beberapa gerbong disimpan di dalam $2$ depo. Di dalam masing-masing depo, gerbong-gerbong berjajar dalam satu barisan. Saat menyusun kereta, gerbong dikeluarkan dari depo lalu digandengkan di depan depo. Gerbong yang dapat dikeluarkan dari depo hanyalah gerbong yang paling dekat dengan pintu masuk depo tersebut, tetapi urutan dari depo mana gerbong dikeluarkan bebas ditentukan.

Sebelum mulai menyusun kereta, sebanyak apa pun gerbong dapat dikeluarkan dari depo dan dipindahkan ke rel tunggu terpisah. Gerbong yang sudah dipindahkan ke rel tunggu tidak dapat digunakan lagi untuk menyusun kereta. Selain itu, begitu penyusunan kereta dimulai, tidak ada gerbong yang boleh dipindahkan dari depo ke rel tunggu sampai penyusunan kereta tersebut selesai.

Saat menyusun kereta, tidak perlu menghabiskan semua gerbong yang ada di dalam depo. Artinya, setelah selesai menyusun kereta, gerbong yang tidak terpakai boleh tetap tersisa di dalam depo.

Karena diperkirakan akan ada sangat banyak orang yang menaiki kereta api di Kerajaan IOI, kita ingin menyusun kereta sepanjang mungkin.

Gambar: Di tengah proses penyusunan kereta (atas: rel tunggu; kiri bawah: kereta yang sedang disusun; kanan: depo S dan depo T); pada saat ini gerbong di dalam depo tidak dapat dipindahkan ke rel tunggu. Gambar ini sesuai dengan Contoh 1.

Tugas

Diberikan informasi mengenai gerbong-gerbong yang disimpan di dalam depo, buatlah program untuk mencari nilai maksimum panjang kereta yang dapat disusun. Barisan gerbong yang disimpan di masing-masing depo dinyatakan oleh string yang hanya terdiri dari $2$ jenis karakter I dan O, dan informasi dari $2$ depo tersebut masing-masing diberikan sebagai string $S$ dengan panjang $M$ dan string $T$ dengan panjang $N$. Setiap karakter menyatakan $1$ gerbong, dan karakter tersebut sama dengan jenis gerbongnya. Karakter ke-$1$ dari string menyatakan gerbong yang paling dekat dengan pintu masuk depo, dan karakter terakhir menyatakan gerbong yang berada paling dalam di depo.

Batasan

• $1 \le M \le 2\,000$: panjang string $S$.
• $1 \le N \le 2\,000$: panjang string $T$.

Masukan

Bacalah data berikut dari masukan standar.

• Pada baris ke-$1$, tertulis $M, N$ yang dipisahkan oleh spasi.
• Pada baris ke-$2$, tertulis string $S$.
• Pada baris ke-$3$, tertulis string $T$.

Keluaran

Keluarkan ke keluaran standar dalam $1$ baris sebuah bilangan bulat yang menyatakan nilai maksimum panjang kereta yang dapat disusun. Jika tidak ada $1$ pun kereta yang dapat disusun, keluarkan 0.

Kriteria Penilaian

• Dari data penilaian, untuk $20\%$ dari total nilai, berlaku $M \le 10$, $N \le 10$.
• Dari data penilaian, untuk $50\%$ dari total nilai, berlaku $M \le 50$, $N \le 50$.

Contoh 1

5 5
OIOOI
OOIOI

7

Misalkan depo yang dinyatakan oleh $S$ adalah depo S, dan depo yang dinyatakan oleh $T$ adalah depo T. Pada keadaan ini, misalnya setelah mengeluarkan $1$ gerbong pertama dari depo S dan $2$ gerbong pertama dari depo T ke rel tunggu, jika kita mengeluarkan gerbong dengan urutan depo S, depo S, depo T, depo S, depo S, depo T, depo T, maka kita dapat menyusun kereta IOIOIOI dengan panjang $7$.

Selain itu, setelah mengeluarkan $1$ gerbong pertama dari depo S dan $2$ gerbong pertama dari depo T ke rel tunggu, kita juga dapat menyusun kereta sepanjang $7$ dengan mengeluarkan gerbong dalam urutan depo T, depo T, depo S, depo S, depo T, depo S, depo S. Karena tidak mungkin menyusun kereta yang lebih panjang dari ini, keluarkan $7$.

Contoh 2

5 9
IIIII
IIIIIIIII

1

Perhatikan bahwa kereta I yang hanya terdiri dari $1$ gerbong juga memenuhi syarat sebagai kereta.