题目内容

公司的一份文本 $S$ 中包含一个敏感词 $P$，根据安全规范，$S$ 中不能出现 $P$ 作为子串。

你可以按序删除 $S$ 中的字符，每次删除会将对应位置替换为一个占位符（例如空白），删除操作不会导致剩余字符前后拼接。现有一个预定的删除顺序，用一个长度为 $n$ 的排列 $a$ 表示，其中 $a_i$ 表示第 $i$ 次删除的字符位置。

请你计算：最少需要执行多少次删除（即选择最小的 $k$，执行前 $k$ 次删除），才能保证处理后的文本中不再包含敏感词 $P$ 作为子串。

约束条件：

• 文本 $S$ 的长度 $n$ 不超过 $10^5$。
• 敏感词 $P$ 的长度 $m$ 不超过 $50$。
• 整数 $a_i$ 均在 $1$ 到 $n$ 之间，且构成一个排列。
• 字符串仅包含小写字母。

输入描述

第一行包含两个整数 $n$ 和 $m$，分别表示文本 $S$ 的长度和敏感词 $P$ 的长度。 第二行包含一个长度为 $n$ 的字符串 $S$，仅由小写字母组成。 第三行包含一个长度为 $m$ 的字符串 $P$，仅由小写字母组成。 第四行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示删除顺序的排列，每个整数均在 $1$ 到 $n$ 之间且互不相同。

输出描述

输出一个整数，表示最少需要执行的删除次数。

样例1

输入

4 2
abab
ab
1 3 2 4

输出

2

说明

文本 $S = \texttt{abab}$，敏感词 $P = \texttt{ab}$，删除顺序为 $[1, 3, 2, 4]$。 初始时存在两个匹配子串：位置 1 到 2 的 $\texttt{ab}$ 和位置 3 到 4 的 $\texttt{ab}$。 第 1 次删除位置 1，破坏第一个匹配，但位置 3 到 4 的子串 $\texttt{ab}$ 仍完整存在。 第 2 次删除位置 3，破坏第二个匹配，此后文本中不再包含敏感词。 因此最少需要执行 2 次删除。

样例2

输入

5 5
hello
world
5 4 3 2 1

输出

0

说明

文本 $S = \texttt{hello}$，敏感词 $P = \texttt{world}$。$S$ 中完全不存在子串等于 $P$，因此不需要执行任何删除操作（$k = 0$）。删除顺序不影响结果，答案为 0。

样例3

输入

5 3
ababa
aba
3 1 2 4 5

输出

1

说明

文本 $S = \texttt{ababa}$，敏感词 $P = \texttt{aba}$。存在两个重叠的匹配：位置 1 到 3 的 $\texttt{aba}$ 和位置 3 到 5 的 $\texttt{aba}$，它们共享位置 3 的字符 $\texttt{b}$。 第 1 次删除位置 3，该字符被移除，两个匹配同时被破坏，剩余文本中不再存在完整的 $P$。因此最少删除次数为 1。

样例4

输入

4 2
aaaa
aa
1 2 3 4

输出

3

说明

文本 $S = \texttt{aaaa}$，敏感词 $P = \texttt{aa}$。匹配位置为 1-2、2-3 和 3-4。 删除顺序 $[1, 2, 3, 4]$：

• 执行前 1 次删除（位置 1）：匹配 2-3、3-4 仍完整，仍包含敏感词。
• 执行前 2 次删除（位置 1, 2）：匹配 3-4 仍完整，仍包含敏感词。
• 执行前 3 次删除（位置 1, 2, 3）：所有长度为 2 的窗口都至少有一个字符被删除，不再包含敏感词。 因此最少需要 3 次删除。