题目描述

题目译自 XX Olimpiada Informatyczna — III etap Łańcuch kolorowy

小 Bajtuś 酷爱玩弄五彩缤纷的链子，收集了一大堆，但他对每条链子的喜爱程度各不相同。每条链子由若干彩色链环组成。Bajtazar 发现，Bajtuś 的审美品味极为挑剔：他认为链子的某个连续片段漂亮，当且仅当该片段包含正好 $l_1$ 个颜色 $c_1$ 的链环、$l_2$ 个颜色 $c_2$ 的链环、……、$l_m$ 个颜色 $c_m$ 的链环，且不含其他颜色的链环。一条链子的吸引力取决于其中漂亮连续片段的数量。Bajtazar 通过反复尝试，摸清了 $c_1, \ldots, c_m$ 和 $l_1, \ldots, l_m$ 的值。现在，他想为 Bajtuś 选购一条新链子，请你编写程序，帮他计算链子的吸引力。

输入格式

• 第一行包含两个整数 $n$, $m$ ($1 \leq m \leq n \leq 1\,000\,000$)，分别表示链子长度和漂亮片段的描述长度。
• 第二行包含 $m$ 个整数 $l_1, \ldots, l_m$ ($1 \leq l_i \leq n$)，表示漂亮片段中各颜色链环的数量。
• 第三行包含 $m$ 个整数 $c_1, \ldots, c_m$ ($1 \leq c_i \leq n$, $c_i \neq c_j$ 当 $i \neq j$)，表示漂亮片段中各颜色的编号。
• 第四行包含 $n$ 个整数 $a_1, \ldots, a_n$ ($1 \leq a_i \leq n$)，表示链子各链环的颜色。

输出格式

输出一行，包含一个整数，表示链子中漂亮连续片段的数量。

样例

输入

7 3
2 1 1
1 2 3
4 2 1 3 1 2 5

输出

2

解释
此链子的两个漂亮片段为 2 1 3 1 和 1 3 1 2。

附加样例

1. $n=9$, $m=3$，两个漂亮片段依次出现，不重叠。
2. $n=10$, $m=5$，漂亮片段长度超过链子长度，结果 $0$。
3. $n=19$, $m=7$，三个漂亮片段相互重叠。
4. $n=1000$, $m=500$，漂亮片段包含颜色 $\{1, \ldots, 500\}$ 各一个，链子为颜色序列 $1, 2, \ldots, 499, 500, 500, 499, \ldots, 2, 1$，结果 $2$。
5. $n=1\,000\,000$, $m=2$，漂亮片段包含 $1$ 个颜色 $1$ 和 $2$ 个颜色 $2$，链子为 $1, 2, 2, 1, 2, 2, \ldots$，结果 $999\,998$。

数据范围与提示

• 对于 $50\%$ 的测试数据，$1 \leq m \leq n \leq 5\,000$。