19367번 - Compressed LCS 다국어

문제

Bobo has two integer sequences $A$ and $B,ドル both in compressed form. $A = c_1^{a_1} c_2^{a_2} \dots c_n^{a_n}$ means that $A$ begins with $a_1$ copies of the integer $c_1,ドル followed by $a_2$ copies of the integer $c_2,ドル $a_3$ copies of the integer $c_3,ドル and so on. $B = d_1^{b_1} d_2^{b_2} \dots d_m^{b_m}$ is of similar format.

Bobo would like to find the LCS (longest common subsequence) for $A$ and $B$. Recall that sequence $C$ is a subsequence of $A$ if and only if $C$ can be obtained by deleting some (maybe all, maybe none) elements from $A$.

입력

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

The first line contains two integers $n$ and $m$ (1ドル \leq n, m \leq 2000$).

The $i$-th of the following $n$ lines contains two integers $c_i$ and $a_i$. And the $i$-th of the last $m$ lines contains two integers $d_i$ and $b_i$.
The constraints are: 1ドル \leq a_i, b_i, c_i, d_i, \sum\limits_{i = 1}^n a_i, \sum\limits_{i = 1}^m b_i \leq 10^9,ドル $c_i \neq c_{i - 1},ドル $d_i \neq d_{i - 1}$.

It is guaranteed that the sum of $n$ and the sum of $m$ both do not exceed 2000ドル$.

출력

For each test case, output an integer which denotes the length of the LCS.

제한

힌트