32820번 - Covers 다국어

문제

You are given two strings $T$ and $P$. Your aim is to create $T$ with $P$. You first begin with an empty string. Then you can do one of three operations shown below.

• Put $P$ at the end of the current string. This operation costs 0ドル$.
• Put a character at the end of the current string. This operation costs 1ドル$.
• Delete characters at the end of the current string and put $P$. This operation costs the number of characters you deleted.

For example, assume that $T = $aabaabaa and $P = $aaba. There are two ways to create $T$ with $P$ as follows, where ε denotes an empty string.

• ε → aaba → aabaa → aabaab → aabaaba → aabaabaa, or
• ε → aaba → aab → aabaaba → aabaabaa.

The former costs four as it first puts $P$ (cost 0ドル$) and four characters (a, b, a, and a, cost 4ドル$). The latter costs two as it first puts $P$ (cost 0ドル$), then deletes one character (a, cost 1ドル$) and puts $P$ (cost 0ドル$), and finally puts a character (a, cost 1ドル$). We choose the latter and we can see that it has the minimum cost.

Given $T$ and $P,ドル write a program which computes the minimum cost to create $T$ with $P$.

입력

Your program is to read from standard input. The input starts with a line containing two integers, $m$ and $n$ (1ドル ≤ m ≤ 100,000円,ドル 1ドル ≤ n ≤ 200,000円$), where $m$ is the length of $P$ and $n$ is that of $T$. The second line contains $P$ and the third line contains $T$. Both $P$ and $T$ are in English lower-case letters.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the minimum cost to create $T$ with $P$.

제한

힌트