×

计蒜客

  1. 题库
  2. Longest subsequence
  3. 问答
  • 17.22%
  • 131072K

String is a very useful thing and a subsequence of the same string is equally important.

Now you have a string $s$ with length $n$ and a string $t$ with length $m$. Find out the longest subsequence in the string $s$ so that the lexicographical order of this subsequence is strictly larger than $t$.

Input

two integers $n$, $m$ in the first line 

(All characters are lowercase letters)

The second line is a string $s$

The third line is a string $t$

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

Output

Output an integer representing the longest length, otherwise output -1.

样例输入

9 3
aaabbbccc
abc

样例输出

6

想挑战这道题吗

  • main.c