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, \ldots, 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, \ldots, c_m and l_1, \ldots, 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

The first line of the standard input gives two integers, n and m, 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, \ldots, l_m, separated by single spaces. The third line gives m integers, c_1, \ldots, c_m, also separated by single spaces. The sequences l_1, \ldots, l_m and c_1, \ldots, 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, \ldots, a_n, separated by single spaces, that are the colors of successive links of the chain.

Output

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.

Constraints

• 1 \le m \le n \le 10^6
• 1 \le l_i \le n
• 1 \le c_i \le n, c_i \neq c_j for i \neq j
• 1 \le a_i \le n

Example

For the input data:

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

the correct result is:

2

Explanation of the example: The two nice fragments of this chain are 2, 1, 3, 1 and 1, 3, 1, 2.

Task author: Tomasz Walen.