P15149 [SWERC 2024] Phryctoria

Lusius Quietus, one of the generals of Trajan, the Roman emperor, is sending signals to his army using signal towers like the one above, where the fires you lit can be seen from afar. He wants to send the string $S$ describing military manoeuvres. However, sending long messages via fire signals is time-consuming, so Lusius decides to use a shorthand system. To abbreviate the message, Lusius can replace any substring of $S$ with the special character `*`. For example, if $S$ is `"swerc"`, then some possible abbreviations are: `"swe*"` , `"*sw*r*"` , `"swerc"` , `"*"` , etc. Note that `*` can match the whole string or no character at all, so `"*sw*r*"` is indeed considered a valid abbreviation of `"swerc"` even though it’s longer (Lusius is not always clever). However, there is a problem: the recipient might misinterpret Lusius’s message. If the abbreviation he sends is also a valid abbreviation of the string $T$, which is a word used to signal retreat, it could lead to losing the war. Help Lusius find the length of the shortest possible abbreviation of $S$ that cannot be interpreted as an abbreviation of $T$.

The first line contains two integers $N$ and $M$, the lengths of the strings $S$ and $T$, respectively. The second line contains the string $S$. The third line contains the string $T$.

The length of the shortest abbreviation of $S$.

### Sample Explanation A possible solution is “sw*”. ### Limits - $1 \le N \le 500$ - $1 \le M \le 500$ - $S \ne T$ - $S$ and $T$ contain only lowercase English letters.