D2 - Substri18ng

問題

正整数 $N$ と長さが $N$ の正整数列 $A^S$ と長さが $N$ の文字列 $T^S$ が与えられます。
また、正整数 $M$ と長さが $M$ の正整数列 $A^G$ と長さが $M$ の文字列 $T^G$ が与えられます。
文字列 $X$ は、空文字列に以下の操作を $1\leq i \leq N$ を満たす $i$ それぞれに小さい順に繰り返して得られる文字列です。

• 文字列に $A^X_i$ 回 $T^X_i$ を追加する

簡単に言うと、 文字列 $S, G$ が連長圧縮した形式で文字群を $T^S, T^G$ 、長さ群を $A^S, A^G$ として与えられます。

このとき、文字列 $G$ と一致する $S$ の部分文字列の個数を出力してください。

制約

• $1\leq N, M\leq 2\times 10^5$
• $T^S_i \neq T^S_{i+1}$
• $T^G_i \neq T^G_{i+1}$
• $1\leq A^S_i, A^G_i \leq 10^9$
• $|A^S|=N,|A^G| = M$
• $T^S, T^G$ は英小文字からなる長さがそれぞれ $N, M$ の文字配列
• $N,M,A^S_i, A^G_i$ は整数

小課題

• 小課題1 (5点)
  • $M\leq 2$
• 小課題2 (100点)
  • $\sum_i A^S_i\leq 100$
  • $\sum_i A^G_i\leq 100$
• 小課題3 (95点)
  • $\sum_i A^S_i\leq 2\times 10^5$
  • $\sum_i A^G_i\leq 2\times 10^5$
• 小課題4 (70点)
  • $M\leq 100$
• 小課題5 (180点)
  • 追加の制約はありません。

入力

入力は以下の形式で標準入力から与えられます。

$N$

$T^S_1~A^S_1$

$T^S_2~A^S_2$

$\vdots$

$T^S_{N-1}~A^S_{N-1}$

$T^S_N~A^S_N$

$M$

$T^G_1~A^G_1$

$T^G_2~A^G_2$

$\vdots$

$T^G_{M-1}~A^G_{M-1}$

$T^G_M~A^G_M$

入力例1

3
c 5
b 25
a 7
2
b 3
a 7
Copy

この入力はすべての小課題の制約を満たします。

出力例1

1
Copy

$S$ は ccccbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaa、$T$ は bbbaaa となるので答えは 1 です。

入力例2

5
c 9
a 3
c 10
b 10
c 7
5
a 2
c 5
a 5
c 4
b 10
Copy

この入力は小課題 2, 3, 4, 5 の制約を満たします。

出力例2

0
Copy

入力例3

5
a 7
b 4
c 6
a 9
c 3
3
b 2
c 6
a 6
Copy

この入力は小課題 2, 3, 4, 5 の制約を満たします。

出力例3

1
Copy