AdditionalFile5016.zip

#5016. 「POI2013 R3」彩链 Colorful Chain

标签: 传统 | 时间限制: 4500 ms | 内存限制: 128 MiB |

题目描述

题目译自 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 1000000)$，分别表示链子长度和漂亮片段的描述长度。

第二行包含 $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 \text{ 当 } 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=1000000, m=2$，漂亮片段包含 $1$ 个颜色 $1$ 和 $2$ 个颜色 $2$，链子为 $1, 2, 2, 1, 2, 2, \ldots$，结果 $999998$。

数据范围与提示

对于 $50\%$ 的测试数据，$1 \leq m \leq n \leq 5000$。