Run, IOI Train

The nation of IOI has opened a new line, the IOI Line.

An IOI train is several single-cell unit cars joined in a row, and each unit car is one of two kinds: I or O.

For safety, adjacent cars must be of different kinds, and because the driver's cab exists only in an I car, both end cars of the train must be I. A valid train therefore starts and ends with I and alternates I and O (for example I, IOI, IOIOI, ...), so its length is always odd. Trains such as OIOI or IOOI are not valid.

A train is written as the string of car kinds from front to back, and the length of that string is the length of the train. For example IOIOI has length 5, and I is a train of length 1.

The unit cars are parked in two garages, S and T, each in a single line. A car cannot be lifted out of place, so from each garage you may only take cars in order starting from the one nearest the entrance (the front).

Before assembly begins, you may move any number of front cars out of each garage to external storage in advance (that is, you may discard any prefix of each garage). Cars sent to external storage cannot be used. Once assembly begins you can no longer send cars to external storage, so from then on every car you take out of a garage must be appended to the train.

When assembly begins, you repeatedly take the front car of either garage and append it to the end of the train you have built so far, stopping whenever you like. Making the resulting train a valid IOI train, find the maximum possible length of the train.

The first line contains the number of cars N parked in garage S and the number of cars M parked in garage T. ($1 \le N, M \le 2000$)

The second line contains a string of length N describing the cars in garage S.

The third line contains a string of length M describing the cars in garage T.

The first character of each string is the car parked nearest that garage's entrance.

Print, on one line, the maximum length of a valid IOI train that can be built.

If no train can be built, print 0.