10006번 - Colorful Chain 다국어

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₁ links of color c₁,l₂ links of color c₂,…,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₁,…,c_m and l_m,…,l_m. Now he would like to buy a new chain, and therefore asks you to write a program to aid him in shopping.

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₁,…,l_m (1 ≤ l_i ≤ n), separated by single spaces. The third line gives m integers, c₁,…,c_m (1 ≤ c_i ≤ n, c_i≠c_j for i≠j), also separated by single spaces. The sequences l₁,…,l_m and c₁,…,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₁,…,a_n(1 ≤ a_i ≤ n), separated by single spaces, that are the colors of successive links of the chain.

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.

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