#P18418. LCSLCSLCS

LCSLCSLCS

LCSLCSLCS

给定两个非空字符串 A,BA,B,它们都由大写英文字母组成,且 ∣A∣,∣B∣≤500|A|,|B|\le500。另外给定两个整数 n,mn,m,满足 1≤n,m≤10151\le n,m\le10^{15}。

记 AnA^n 为将 nn 份字符串 AA 依次连接得到的字符串,BmB^m 的含义类似。求 AnA^n 与 BmB^m 的最长公共子序列的长度。

子序列允许删除字符,保留下来的字符须保持原有相对顺序,不要求连续。

输入格式

第一行包含两个整数 n,mn,m,满足 1≤n,m≤10151\le n,m\le10^{15}。

第二行包含一个非空字符串 AA,第三行包含一个非空字符串 BB。两串长度均不超过 500500,且仅包含大写英文字母 A 到 Z。

输出格式

输出一个整数,表示 AnA^n 与 BmB^m 的最长公共子序列的长度。

样例 1

输入:

10 10
AB
BA

输出:

19

样例 2

输入:

100000000 100000000
A
AB

输出:

100000000