Bobo 有两个压缩形式的整数序列 $A$ 和 $B$。$A = c_1^{a_1} c_2^{a_2} \dots c_n^{a_n}$ 表示 $A$ 以 $a_1$ 个整数 $c_1$ 开头，接着是 $a_2$ 个整数 $c_2$，$a_3$ 个整数 $c_3$，以此类推。$B = d_1^{b_1} d_2^{b_2} \dots d_m^{b_m}$ 的格式与之类似。

Bobo 想要找到 $A$ 和 $B$ 的 LCS（最长公共子序列）。回想一下，序列 $C$ 是 $A$ 的子序列，当且仅当 $C$ 可以通过从 $A$ 中删除某些（可能全部，也可能不删除）元素得到。

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 2000$)。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $c_i$ 和 $a_i$。最后 $m$ 行中，第 $i$ 行包含两个整数 $d_i$ 和 $b_i$。约束条件为：$1 \le a_i, b_i, c_i, d_i$，$ \sum_{i=1}^n a_i, \sum_{i=1}^m b_i \le 10^9$，$c_i \neq c_{i-1}$，$d_i \neq d_{i-1}$。

保证 $n$ 的总和与 $m$ 的总和均不超过 $2000$。

对于每个测试用例，输出一个整数，表示 LCS 的长度。

样例

输入格式 1

1 3
1 2
1 1
2 1

输出格式 1

2

输入格式 2

1 2
4 4
1 1
2 1
3 1
4 1

输出格式 2

3

输入格式 3

1 1
3 1
2 1
4 1
1 1
1000000000 999
1000000000 1000

输出格式 3

999