lcs(2s,1024MB)

题目描述

给定两个序列 $A,B$，求 $A,B$ 的最长公共子序列。

其中 $A=c_1^{a_1}c_2^{a_2}...c_n^{a_n},B=d_1^{b_1}d_2^{b_2}...d_m^{b_m}$，$c^a$ 表示 $c$ 重复 $a$ 次。

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行，每行两个整数 $c_i,a_i$

接下来 $m$ 行，每行两个整数 $d_i,b_i$

输出格式

一行一个整数，表示答案。

样例输入1

1 1
1 1
1 1

样例输出1

1

数据范围与约束

$\text{subtask1(10 pts):}\ \sum a_i,\sum b_i \le 1000$

$\text{subtask2(20 pts):}\ n,m \le 100$

$\text{subtask3(30 pts):}\ n,m \le 1000$

$\text{subtask4(40 pts):}$ 无特殊限制

$1\le n,m \le 2000,1\le a_i,b_i,c_i,d_i,\sum a_i,\sum b_i\le 10^9$