Testo del problema

Nel Regno di IOI è stata recentemente costruita una nuova ferrovia. Un treno che circola sulla ferrovia del Regno di IOI è costituito da diverse carrozze agganciate tra loro, ed esistono $2$ tipi di carrozze: I e O. Ogni carrozza può essere agganciata solo a una carrozza di tipo diverso. Inoltre, poiché occorre installare le cabine di guida a entrambe le estremità del treno, le carrozze situate alle due estremità di un treno devono essere di tipo I. Un treno è rappresentato da una stringa ottenuta concatenando nell'ordine i caratteri che indicano i tipi delle sue carrozze, e la lunghezza del treno è definita come la lunghezza di tale stringa. Ad esempio, agganciando le carrozze nell'ordine IOIOI si può formare un treno di lunghezza $5$, e una singola carrozza I da sola costituisce un treno di lunghezza $1$. Non è possibile formare un treno disponendo le carrozze in un ordine come OIOI oppure IOOI.

Diverse carrozze sono custodite in $2$ depositi. All'interno di ciascun deposito, le carrozze sono allineate in un'unica fila. Quando si forma un treno, si fanno uscire le carrozze dai depositi e le si aggancia davanti ai depositi. L'unica carrozza che può uscire da un deposito è quella più vicina all'ingresso di quel deposito, ma l'ordine con cui si sceglie da quale dei due depositi far uscire le carrozze è libero.

Prima di iniziare a formare un treno, è possibile far uscire dai depositi quante carrozze si vuole e spostarle su un binario di attesa separato. Le carrozze spostate sul binario di attesa non potranno più essere utilizzate in seguito per formare il treno. Inoltre, una volta iniziata la formazione del treno, non è più possibile spostare carrozze dai depositi al binario di attesa fino al termine della formazione.

Quando si forma un treno, non è necessario utilizzare tutte le carrozze presenti nei depositi. In altre parole, una volta terminata la formazione del treno, nei depositi possono rimanere delle carrozze inutilizzate.

Poiché si prevede che nel Regno di IOI moltissime persone prenderanno il treno, si desidera formare un treno il più lungo possibile.

Figura: Durante la formazione di un treno (in alto: binario di attesa; in basso a sinistra: treno in formazione; a destra: deposito S e deposito T); in questo momento non è possibile spostare sul binario di attesa le carrozze presenti nei depositi. Questa figura corrisponde all'Esempio 1.

Compito

Date le informazioni sulle carrozze custodite nei depositi, scrivi un programma per determinare la massima lunghezza possibile di un treno che può essere formato. La fila di carrozze custodita in ciascun deposito è rappresentata da una stringa composta solo dai $2$ tipi di caratteri I e O, e le informazioni dei $2$ depositi sono date rispettivamente come una stringa $S$ di lunghezza $M$ e una stringa $T$ di lunghezza $N$. Ogni carattere rappresenta $1$ carrozza e coincide con il tipo della carrozza. Il $1$-o carattere della stringa rappresenta la carrozza più vicina all'ingresso del deposito, mentre l'ultimo carattere rappresenta la carrozza più in fondo al deposito.

Vincoli

• $1 \le M \le 2\,000$: la lunghezza della stringa $S$.
• $1 \le N \le 2\,000$: la lunghezza della stringa $T$.

Input

Leggi i seguenti dati dallo standard input.

• Sulla $1$-a riga sono scritti $M, N$ separati da uno spazio.
• Sulla $2$-a riga è scritta la stringa $S$.
• Sulla $3$-a riga è scritta la stringa $T$.

Output

Stampa sullo standard output, su $1$ sola riga, l'intero che rappresenta la massima lunghezza possibile di un treno che si può formare. Se non è possibile formare nemmeno $1$ treno, stampa 0.

Criteri di valutazione

• Per il $20\%$ del punteggio totale, valgono $M \le 10$, $N \le 10$.
• Per il $50\%$ del punteggio totale, valgono $M \le 50$, $N \le 50$.

Esempio 1

5 5
OIOOI
OOIOI

7

Chiamiamo deposito S il deposito rappresentato da $S$ e deposito T il deposito rappresentato da $T$. Allora, ad esempio, dopo aver fatto uscire e messo in attesa la prima ($1$) carrozza dal deposito S e le prime $2$ carrozze dal deposito T, se facciamo uscire le carrozze nell'ordine: deposito S, deposito S, deposito T, deposito S, deposito S, deposito T, deposito T, possiamo formare il treno IOIOIOI di lunghezza $7$.

Inoltre, dopo aver fatto uscire e messo in attesa la prima ($1$) carrozza dal deposito S e le prime $2$ carrozze dal deposito T, possiamo formare un treno di lunghezza $7$ anche facendo uscire le carrozze nell'ordine: deposito T, deposito T, deposito S, deposito S, deposito T, deposito S, deposito S. Poiché non è possibile formare un treno più lungo di così, si stampa $7$.

Esempio 2

5 9
IIIII
IIIIIIIII

1

Si noti che anche il treno I composto da $1$ sola carrozza soddisfa le condizioni per essere un treno.