题目描述

给定两个序列 $X$ 和 $Y$ ，当另一序列 $Z$ 既是 $X$ 的子序列又是 $Y$ 的子序列时，称 $Z$ 是序列 $X$ 和 $Y$ 的公共子序列。

例如，若 $X＝<A,B,C,B,D,A,B>$ 和 $Y＝<B,D,C,A,B,A>$ ，则序列 $<B,C,A>$ 是 $X$ 和 $Y$ 的一个公共子序列，序列 $<B,C,B,A>$ 也是 $X$ 和 $Y$ 的一个公共子序列。而且，后者是 $X$ 和 $Y$ 的一个最长公共子序。因为 $X$ 和 $Y$ 没有长度大于 $4$ 的公共子序列。

给定两个序列 $X＝<x_1,x_2,\cdots,x_m>$ 和 $Y=<y_1,y_2,\cdots,y_n>$ 要求找出 $X$ 和 $Y$ 的一个最长公共子序列。

输入格式

第一行输入两个正整数 $n,m\ (1\le n,m \le 10^3)$，分别表示序列 $X,Y$ 的长度。

下面两行。每行为一个由大写字母构成的长度不超过 $10^3$ 的字符串，表示序列 $X$ 和 $Y$ 。

输出格式

一行一个整数，表示所求得的最长公共子序列的长度。

输入样例

7 6
ABCBDAB
BDCABA

输出样例

4