题目描述

对于两个给定的序列，请求出它们的最长公共子序列长度。

一个序列的子序列定义为能通过删除一部分元素，保留剩下的元素相对顺序不变而得到的序列。

输入格式

第一行两个整数 $n,m$，表示两个序列的长度。

第二行 $n$ 个整数 $a_1,a_2, \ldots ,a_n$，表示第一个序列。

第二行 $m$ 个整数 $b_1,b_2, \ldots ,b_m$，表示第二个序列。

输出格式

输出两个序列的最长公共子序列长度。

4 5
1 2 4 5
4 1 3 3 2

2

数据范围与提示

本题共有两个子任务。

对于所有数据，$1 \leq n,m,a_i,b_i \leq 70000$。

Subtask 1（50分）：$n,m \leq 5000$。

Subtask 2（50分）：无特殊限制。

数据是瞎随机的，可能挺弱的，欢迎hack。