题目描述

给定两个由小写英文字母组成的字符串，请求出它们的最长公共子序列长度。子序列可以通过删除原字符串中的若干字符得到，但不能改变剩余字符的先后顺序。

输入格式

第一行输入两个整数 $N,M$。

第二行输入长度为 $N$ 的字符串 $A$，第三行输入长度为 $M$ 的字符串 $B$。

输出格式

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

数据范围与约定

$1\le N,M\le 1000$；字符串仅含小写英文字母。

可见测试数据

输入数据 1

4 5
acbd
abedc

输出数据 1

3

输入数据 2

10 10
nqunjucfgh
irsfovvqah

输出数据 2

2

输入数据 3

3 7
akk
anoipak

输出数据 3

2