说明

卢修斯·奎图斯（Lusius Quietus）是罗马皇帝图拉真麾下的一名将军，他正在使用如上图所示的信号塔向他的军队发送信号，点燃的火焰可以从远处看到。

他希望发送描述军事调动的字符串 $S$。然而，通过火焰信号发送长消息非常耗时，因此卢修斯决定使用一种速记系统。为了缩写消息，卢修斯可以将 $S$ 的任意子串替换为特殊字符 *。例如，如果 $S$ 是 swerc，那么一些可能的缩写包括：swe*、*sw*r*、swerc、* 等。注意 * 可以匹配整个字符串或不匹配任何字符，因此 *sw*r* 确实被视为 swerc 的有效缩写，尽管它更长（卢修斯并不总是聪明）。

然而，有一个问题：接收者可能会误解卢修斯的消息。如果他发送的缩写同时也是字符串 $T$ 的有效缩写（$T$ 是用于表示撤退的信号词），就可能导致输掉战争。

请帮助卢修斯找出 $S$ 的最短缩写长度，使得该缩写不能被解释为 $T$ 的缩写。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示字符串 $S$ 和 $T$ 的长度。第二行包含字符串 $S$。第三行包含字符串 $T$。

输出格式

输出 $S$ 的最短缩写长度。

5 5
swerc
seerc

3

提示

样例解释

一个可能的解是 sw*。

数据范围

• $1 \le N \le 500$
• $1 \le M \le 500$
• $S \ne T$
• $S$ 和 $T$ 仅包含小写英文字母。

翻译由 DeepSeek 完成