Nước IOI vừa xây dựng một tuyến đường sắt mới. Mỗi đoàn tàu chạy trên đường sắt của nước IOI được tạo thành bằng cách nối các toa tàu. Có hai loại toa, I và O; hai toa chỉ có thể nối với nhau nếu khác loại. Ngoài ra, để bố trí buồng lái, cả hai toa ở hai đầu đoàn tàu đều phải thuộc loại I.

Một đoàn tàu được biểu diễn bằng xâu tạo bởi các chữ cái chỉ loại toa theo đúng thứ tự, và độ dài của đoàn tàu là độ dài xâu đó. Chẳng hạn, nối các toa theo thứ tự IOIOI tạo thành một đoàn tàu dài \(5\); một toa I đứng riêng cũng là đoàn tàu dài \(1\). Các cách xếp OIOI hoặc IOOI không tạo thành đoàn tàu hợp lệ.

Một số toa tàu đang được cất trong hai nhà chứa toa. Trong mỗi nhà chứa, các toa nằm trên một hàng. Để ghép đoàn tàu, người ta lấy các toa ra khỏi nhà chứa và nối chúng ở phía trước các nhà chứa. Chỉ có thể lấy ra toa gần cửa vào nhất của một nhà chứa, nhưng được tự do chọn nhà chứa để lấy toa ở mỗi lần.

Trước khi bắt đầu ghép đoàn tàu, có thể lấy tùy ý bao nhiêu toa ra khỏi các nhà chứa và chuyển chúng sang một đường ray chờ riêng. Một khi đã chuyển sang đường ray chờ, toa đó không thể được dùng để ghép đoàn tàu nữa. Khi đã bắt đầu ghép đoàn tàu, cho đến lúc ghép xong, không được chuyển toa từ nhà chứa sang đường ray chờ.

Không nhất thiết phải dùng hết các toa trong nhà chứa. Nói cách khác, sau khi ghép xong, có thể vẫn còn các toa chưa được dùng trong nhà chứa.

Dự kiến có rất nhiều người đi đường sắt tại nước IOI, nên người ta muốn ghép một đoàn tàu dài nhất có thể.

Yêu cầu

Cho thông tin các toa trong hai nhà chứa, hãy viết chương trình tìm độ dài lớn nhất của đoàn tàu có thể ghép được.

Các toa trong hai nhà chứa lần lượt được mô tả bằng xâu \(S\) dài \(M\) và xâu \(T\) dài \(N\), chỉ gồm các ký tự I, O. Mỗi ký tự biểu diễn một toa có loại tương ứng. Ký tự đầu tiên là toa gần cửa vào nhất; ký tự cuối cùng là toa nằm sâu nhất trong nhà chứa.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(M,N\), cách nhau bởi dấu cách.
• Dòng thứ hai chứa xâu \(S\).
• Dòng thứ ba chứa xâu \(T\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là độ dài lớn nhất của đoàn tàu có thể ghép được. Nếu không thể ghép được đoàn tàu nào, in ra \(0\).

Ràng buộc

• \(1\le M\le2000\).
• \(1\le N\le2000\).
• \(S\) có độ dài \(M\) và \(T\) có độ dài \(N\); cả hai xâu chỉ gồm các ký tự I, O.

Phân nhóm

• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(M\le10\) và \(N\le10\).
• \(50\%\) số điểm dành cho các dữ liệu thỏa mãn \(M\le50\) và \(N\le50\).

5 5
OIOOI
OOIOI

7

Gọi hai nhà chứa được mô tả bởi \(S\) và \(T\) lần lượt là nhà chứa \(S\) và nhà chứa \(T\). Chẳng hạn, chuyển toa đầu tiên của nhà chứa \(S\) và hai toa đầu tiên của nhà chứa \(T\) sang đường ray chờ, rồi lấy toa lần lượt từ các nhà chứa \(S,S,T,S,S,T,T\). Ta ghép được đoàn tàu IOIOIOI dài \(7\).

Cũng có thể chuyển toa đầu tiên của nhà chứa \(S\) và hai toa đầu tiên của nhà chứa \(T\) sang đường ray chờ, rồi lấy toa theo thứ tự các nhà chứa \(T,T,S,S,T,S,S\) để ghép một đoàn tàu dài \(7\). Không thể ghép đoàn tàu dài hơn, nên in ra \(7\).

5 9
IIIII
IIIIIIIII

1

Lưu ý rằng một toa I đứng riêng cũng thỏa mãn điều kiện của một đoàn tàu.