高速公路上有 N 个收费站按编号 1 \ldots N 排成一列，每个收费站被分配一个小写英文字母作为识别码。按编号顺序排列得到长度为 N 的字符串 S。

小Z必须从收费站 1 到 N **按编号升序通过所有收费站**。通常每通过一个收费站耗时 1，若不采用技巧总耗时为 N。

他持有无限张**折扣通行证**，由长度为 M 的字符串 T 表示。对于长度为 M 的连续区间 [l, l+M-1]，若 S[l..l+M-1] = T，则可将该区间以**耗时 1** 通过（原本耗时 M）。

小Z可以选择 **0 个或多个**这样的区间使用通行证，但所选任意两个区间不得有共同收费站。某个区间末尾与另一个区间开头的收费站**紧邻**是允许的。

若使用 k 张券，则总耗时为 k + (N - kM) = N - k(M-1)。

求通过所有收费站的最小总耗时。

- 第 1 行两个整数 N 和 M；

- 第 2 行长度为 N 的字符串 S；

- 第 3 行长度为 M 的字符串 T。

一行一个整数：最小总耗时。

- 1 \le N \le 10^6

- 1 \le M \le N

- S、T 均为小写英文字母构成的字符串