커버스

두 문자열 $T$와 $P$가 주어진다. 목표는 $P$로 $T$를 만드는 것이다. 빈 문자열에서 시작하며, 아래 세 가지 연산 중 하나를 수행할 수 있다.

• 현재 문자열의 끝에 $P$를 붙인다. 비용은 $0$이다.
• 현재 문자열의 끝에 문자 하나를 붙인다. 비용은 $1$이다.
• 현재 문자열의 끝에서 문자를 삭제한 뒤 $P$를 붙인다. 비용은 삭제한 문자의 개수이다.

예를 들어 $T =$ aabaabaa, $P =$ aaba이다. 다음과 같이 $P$로 $T$를 만드는 방법이 두 가지 있다. 여기서 ε는 빈 문자열을 뜻한다.

• ε → aaba → aabaa → aabaab → aabaaba → aabaabaa
• ε → aaba → aab → aabaaba → aabaabaa

첫 번째 방법은 $P$를 먼저 붙이고(비용 $0$), 문자 a, b, a, a 네 개를 붙인다(비용 $4$). 총비용은 4이다. 두 번째 방법은 $P$를 먼저 붙이고(비용 $0$), 문자 a 하나를 삭제한 뒤(비용 $1$) $P$를 다시 붙이고(비용 $0$), 마지막으로 문자 a를 붙인다(비용 $1$). 총비용은 2이다. 두 번째 방법이 최소 비용이다.

$T$와 $P$가 주어졌을 때, $P$로 $T$를 만드는 최소 비용을 구하는 프로그램을 작성하시오.

첫 줄에 두 정수 $m$과 $n$이 주어진다($1 \le m \le 100\,000$, $1 \le n \le 200\,000$). $m$은 $P$의 길이이고, $n$은 $T$의 길이이다. 둘째 줄에는 $P$가, 셋째 줄에는 $T$가 주어진다. $P$와 $T$는 모두 영어 소문자로만 이루어져 있다.

한 줄에 $P$로 $T$를 만드는 최소 비용을 출력한다.