Đề bài

Vương quốc IOI vừa mới xây dựng một tuyến đường sắt mới. Một đoàn tàu chạy trên tuyến đường sắt của Vương quốc IOI gồm một số toa tàu được nối với nhau, và có $2$ loại toa tàu là I và O. Mỗi toa tàu chỉ có thể nối với một toa tàu thuộc loại khác. Ngoài ra, do phải lắp đặt buồng lái ở cả hai đầu đoàn tàu, các toa ở hai đầu đoàn tàu bắt buộc phải thuộc loại I. Một đoàn tàu được biểu diễn bằng một xâu ký tự tạo bởi việc ghép các ký tự thể hiện loại của từng toa theo đúng thứ tự, và độ dài của đoàn tàu được định nghĩa là độ dài của xâu đó. Ví dụ, nối các toa theo thứ tự IOIOI sẽ tạo thành một đoàn tàu có độ dài $5$, và một toa I đứng một mình cũng là một đoàn tàu có độ dài $1$. Không thể lập thành đoàn tàu nếu xếp các toa theo thứ tự như OIOI hay IOOI.

Một số toa tàu đang được cất giữ trong $2$ nhà xe. Bên trong mỗi nhà xe, các toa tàu được xếp thành một hàng dọc. Khi lập đoàn tàu, người ta đưa các toa ra khỏi nhà xe và nối chúng lại với nhau ở phía trước nhà xe. Toa tàu duy nhất có thể đưa ra khỏi một nhà xe là toa nằm gần lối ra vào của nhà xe đó nhất, nhưng thứ tự lựa chọn đưa toa ra từ nhà xe nào trong hai nhà xe là hoàn toàn tự do.

Trước khi bắt đầu lập đoàn tàu, có thể đưa bao nhiêu toa tàu tùy ý ra khỏi nhà xe và chuyển sang một đường ray chờ riêng biệt. Các toa tàu đã chuyển sang đường ray chờ sẽ không thể dùng để lập đoàn tàu sau đó nữa. Đồng thời, một khi đã bắt đầu lập đoàn tàu thì cho đến khi việc lập tàu kết thúc, không thể chuyển các toa từ nhà xe sang đường ray chờ được nữa.

Khi lập đoàn tàu, không nhất thiết phải sử dụng hết tất cả các toa trong nhà xe. Nói cách khác, sau khi hoàn tất việc lập đoàn tàu, trong nhà xe vẫn có thể còn lại những toa chưa được sử dụng.

Vì dự kiến sẽ có rất nhiều người đi tàu hỏa ở Vương quốc IOI, người ta muốn lập một đoàn tàu dài nhất có thể.

Hình vẽ: Đang trong quá trình lập đoàn tàu (phía trên: đường ray chờ; phía dưới bên trái: đoàn tàu đang lập; bên phải: nhà xe S và nhà xe T); tại thời điểm này không thể chuyển toa tàu trong nhà xe sang đường ray chờ. Hình này tương ứng với Ví dụ 1.

Yêu cầu

Cho biết thông tin về các toa tàu được cất giữ trong các nhà xe, hãy viết chương trình tìm giá trị lớn nhất của độ dài đoàn tàu có thể lập được. Dãy các toa tàu trong mỗi nhà xe được biểu diễn bởi một xâu chỉ gồm $2$ loại ký tự I và O, và thông tin của $2$ nhà xe lần lượt được cho dưới dạng xâu $S$ có độ dài $M$ và xâu $T$ có độ dài $N$. Mỗi ký tự biểu diễn $1$ toa tàu, và ký tự đó trùng với loại của toa tàu. Ký tự thứ $1$ của xâu biểu diễn toa tàu gần lối vào nhà xe nhất, và ký tự cuối cùng biểu diễn toa tàu nằm sâu nhất trong nhà xe.

Giới hạn

• $1 \le M \le 2\,000$: độ dài của xâu $S$.
• $1 \le N \le 2\,000$: độ dài của xâu $T$.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng thứ $1$ ghi $M, N$ cách nhau bởi khoảng trắng.
• Dòng thứ $2$ ghi xâu $S$.
• Dòng thứ $3$ ghi xâu $T$.

Kết quả

In ra đầu ra chuẩn trên $1$ dòng một số nguyên biểu thị độ dài lớn nhất của đoàn tàu có thể lập được. Nếu không thể lập được dù chỉ $1$ đoàn tàu, hãy in ra 0.

Tiêu chí chấm điểm

• Trong dữ liệu chấm điểm, $20\%$ số điểm thỏa mãn $M \le 10$, $N \le 10$.
• Trong dữ liệu chấm điểm, $50\%$ số điểm thỏa mãn $M \le 50$, $N \le 50$.

Ví dụ 1

5 5
OIOOI
OOIOI

7

Gọi nhà xe được biểu diễn bởi $S$ là nhà xe S, và nhà xe được biểu diễn bởi $T$ là nhà xe T. Khi đó, ví dụ sau khi đưa $1$ toa đầu tiên từ nhà xe S và $2$ toa đầu tiên từ nhà xe T ra đường ray chờ, nếu ta lấy các toa ra theo thứ tự: nhà xe S, nhà xe S, nhà xe T, nhà xe S, nhà xe S, nhà xe T, nhà xe T, ta có thể lập được đoàn tàu IOIOIOI có độ dài $7$.

Ngoài ra, sau khi đưa $1$ toa đầu tiên từ nhà xe S và $2$ toa đầu tiên từ nhà xe T ra đường ray chờ, nếu lấy các toa ra theo thứ tự: nhà xe T, nhà xe T, nhà xe S, nhà xe S, nhà xe T, nhà xe S, nhà xe S thì cũng lập được đoàn tàu có độ dài $7$. Vì không thể lập được đoàn tàu nào dài hơn thế nên in ra $7$.

Ví dụ 2

5 9
IIIII
IIIIIIIII

1

Lưu ý rằng đoàn tàu I chỉ gồm $1$ toa duy nhất cũng thỏa mãn điều kiện của một đoàn tàu.