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 $l_{1}$ links of color $c_{1},l_{2}$ links of color $c_{2},…,l_{m}$ links of color $c_{m}$, 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 $c_{1},…,c_{m}$ and $l_{1},…,l_{m}$. Now he would like to buy a new chain, and therefore asks you to write a program to aid him in shopping.

Input Format

The first line of the standard input gives two integers, $n$ and $m$ ($1 ≤ m ≤ n ≤ 1\,000\,000$), 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 $m$ integers, $l_{1},…,l_{m}$ ($1 ≤ l_{i} ≤ n$), separated by single spaces. The third line gives m integers, $c_{1},…,c_{m}$ ($1 ≤ c_{i} ≤ n$, $c_{i}≠c_{j}$ for $i≠j$), also separated by single spaces. The sequences $l_{1},…,l_{m}$ and $c_{1},…,c_{m}$ define a nice fragment of a chain - it has to contain exactly $l_{i}$ links of color $c_{i}$. The fourth line gives $n$ integers, $a_{1},…,a_{n}$ ($1 ≤ a_{i} ≤ n$), separated by single spaces, that are the colors of successive links of the chain.

Output Format

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.

Example

Input

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

Output

2

Notes

The two nice fragments of this chain are 2, 1, 3, 1 and 1, 3, 1, 2.