题目描述

给定两个长度分别为 $n, m$ 且仅由小写字母构成的字符串 $A, B$ , 求 $A,B$ 的最长公共子序列。 $(n \le 10^6, m \le 10^3)$

输入格式

第一行包含两个整数 $n, m$ - $n$ 表示 $A$ 的长度， $m$ 表示 $B$ 的长度。 第二行为字符串 $A$ 第三行为字符串 $B$

输出格式

一行一个整数表示最长公共子序列长度。

样例

input

5 6
ababc
bbcbbc

output

3

数据范围与提示

• $n \le 10^6 , m \le 10^3$

字符串仅由小写字母构成

题目来源oi-wiki