题目描述

Little Bytie loves to play with colorful chains.

He already has quite an impressive collection, and some of them he likes more than the others.

Each chain consists of a certain number of colorful links.

Byteasar has noticed that Bytie's sense of aesthetics is very precise.

It turns out that Bytie finds a contiguous fragment of a chain nice if it contains exactly links of color links of color links of color , and moreover it contains no links of other colors.

A chain's appeal is its number of (contiguous) fragments that are nice.

By trial and error, Byteasar has determined the values and .

Now he would like to buy a new chain, and therefore asks you to write a program to aid him in shopping.

给定一个长度为 $n$ 的序列 $a$ 和 $m$ 个条件（每个条件中包含键 $c_i$ 和值 $l_i$），要求找出满足下列条件的子串的数量并输出：

• 条件中存在键 $c_i$ 的，要求子串中 $c_i$ 恰好出现 $l_i$ 次。

• 条件中不存在键 $c_i$ 的，要求子串中不出现 $c_i$。

先输入 $n$ 和 $m$，再输入 $m$ 个条件的 $l_i$，然后输入 $m$ 个条件的 $c_i$，最后输入 $a_i$。

输入格式

The first line of the standard input gives two integers, and (), separated by a single space.

These are the length of the chain and the length of a nice fragment's description.

The second line gives integers, (), separated by single spaces.

The third line gives integers, (, for ), also separated by single spaces.

The sequences and define a nice fragment of a chain - it has to contain exactly links of color .

The fourth line gives integers, (), separated by single spaces, that are the colors of successive links of the chain.

In tests worth 50% of total points the constraint holds in addition.

输出格式

Your program is to print a single integer, the number of nice contiguous fragments in the chain, to the first and only line of the standard output.

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

2

提示

数据范围：

对于 $100\%$ 的数据，$1\leq m\leq n \leq 10^6$，$1\leq a_i,b_i,c_i\leq n$。