古卷对照

题目描述

考古学者得到两份古卷残片，用整数序列表示其中的符号编号： $A = a_1,a_2,\dots,a_n$，$B = b_1,b_2,\dots,b_m$。

为了判定两份残卷是否存在相同的记载，需要计算它们的最长公共子序列（LCS）长度。

请你输出最长公共子序列的长度。

输入格式

输入共三行。

• 第一行包含两个整数 $n,m$。
• 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。
• 第三行包含 $m$ 个整数 $b_1,b_2,\dots,b_m$。

输出格式

输出一行，一个整数，表示最长公共子序列的长度。

输入输出样例 #1

输入 #1

5 6
1 3 4 1 2
3 4 1 2 1 3

输出 #1

4

样例解释 #1

最长公共子序列可以是 3 4 1 2，长度为 $4$。

数据范围

对于所有测试数据，保证：

• $1 \le n,m \le 2000$；
• $1 \le a_i,b_j \le 10^9$。