题目描述

对于两个给定的数组a和b,输出它们的最长公共子序列长度。
一个数组的子序列定义为能通过删除一部分元素,保留剩下的元素相对顺序不变而得到的序列,如序列“1,2”为数组“4,1,3,3,2”的子序列。


输入格式

第一行两个整数 n,m,表示两个数组的长度。
第二行 n 个整数 $a_1$,$a_2$, … ,$a_n$,表示第一个数组。
第三行 m 个整数$ b_1$,$b_2$, … ,$b_m$,表示第二个数组。


输出格式

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


样例数据

输入

4 5
1 2 4 5
4 1 3 3 2 

输出

2

备注

$1 \leq n,m \leq 5000,1 \leq a_i,b_i \leq 10^8$


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

题解