Minimum Repetitions for Maximum LCS

We are given two arrays of positive integers, \(S\) and \(T\), where the length of \(S\) is \(n\) and that of \(T\) is \(m\). In this problem, we define the following:

• For two arrays \(A\) and \(B\), the concatenation \(AB\) is the array obtained by appending \(B\) after \(A\).
• Define \(A^0 = \{\}\) (i.e. the empty array) and for \(i=1,2,3,\dots\), \(A^i = A^{i-1}A\); that is, \(A^i\) is obtained by concatenating \(A\) to \(A^{i-1}\).
• Define \(\operatorname{LCS}(A,B)\) to be the length of the longest common subsequence between \(A\) and \(B\) (a subsequence need not be contiguous).

Now, for a given array \(S\) and \(T\), one can consider the repeated array \(S^k\) for a nonnegative integer \(k\) (with \(S^0\) being empty). As \(k\) increases the longest common subsequence between \(S^k\) and \(T\) may become larger until it reaches a maximum value \(L\) (which is exactly \(\operatorname{LCS}(S^\infty, T)\) where we allow as many copies of \(S\) as needed).

Your task is to find the minimum nonnegative integer \(k\) such that \(\operatorname{LCS}(S^k, T) = L\), i.e. the repeated array \(S^k\) attains the maximum possible longest common subsequence with \(T\).

Note: Since elements in \(T\) that do not appear in \(S\) can never be matched, the maximum LCS is determined by the subsequence of \(T\) that consists of the elements also present in \(S\). In other words, if we define a filtered version \(T'\) of \(T\) which retains only those elements that appear in \(S\) (in the same order), then the maximum LCS is \(|T'|\) and your answer is the minimum number of copies of \(S\) required to form \(T'\) as a subsequence.

If no element of \(T\) appears in \(S\) then the maximum LCS is \(0\) and the answer should be \(0\).

inputFormat

The first line contains two integers \(n\) and \(m\) (the lengths of \(S\) and \(T\) respectively).

The second line contains \(n\) positive integers representing the array \(S\).

The third line contains \(m\) positive integers representing the array \(T\).

outputFormat

Output a single integer, the minimum nonnegative integer \(k\) such that \(\operatorname{LCS}(S^k,T)\) is maximized.

sample

3 5
1 2 3
1 3 2 3 1

3