题目描述

给定一个长度为 $n$ 的整数序列 $A$ 和一个长度为 $m$ 的整数序列 $B$，请你求出它们的最长公共子序列的长度。

一个序列的子序列，是指从原序列中删除若干个元素（也可以不删除），并保持剩余元素的相对顺序不变后得到的序列。子序列中的元素在原序列中不必连续。例如，序列 $1,3,5$ 是 $1,2,3,4,5$ 的子序列，而 $3,1,5$ 不是。

如果一个序列既是 $A$ 的子序列，也是 $B$ 的子序列，那么它就是 $A$ 和 $B$ 的公共子序列。所有公共子序列中，长度最大的称为最长公共子序列（LCS）。

你只需要输出最长公共子序列的长度，不需要输出具体的子序列。如果两个序列没有相同的元素，则答案为 $0$。

输入格式

第一行包含两个整数 $n,m$，分别表示序列 $A$ 和序列 $B$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，依次表示序列 $A$ 中的元素。

第三行包含 $m$ 个整数 $b_1,b_2,\ldots,b_m$，依次表示序列 $B$ 中的元素。

同一行内的相邻整数之间用一个空格分隔。

输出格式

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

7 6
1 3 4 1 2 8 5
3 4 1 2 1 5

5

3 4
1 2 3
4 5 6 7

0

提示

样例 1 解释

序列 $3,4,1,2,5$ 是两个序列的一个公共子序列：

• 在序列 $A$ 中，可以依次选择第 $2,3,4,5,7$ 个元素。
• 在序列 $B$ 中，可以依次选择第 $1,2,3,4,6$ 个元素。 这个公共子序列的长度为 $5$。可以证明这是它们的最长公共子序列。

样例 2 解释

两个序列没有相同的元素，因此最长公共子序列的长度为 $0$。

数据范围

对于 $10\%$ 的数据，$1\leq n,m\leq 10$；

对于 $30\%$ 的数据，$1\leq n,m\leq 100$；

对于 $60\%$ 的数据，$1\leq n,m\leq 1000$；

对于所有测试数据，$1\le n,m\le 5000$，$1\le a_i,b_j\le 10^9$，同一个序列中可以出现重复的元素。