Maximum Repetitions of Subsequence

We define a string (\textbf{str} = [s, n]) as the string obtained by concatenating the string (s) exactly (n) times. For example, (\textbf{str} = [\texttt{abc}, 3] = \texttt{abcabcabc}). A string (s_1) is said to be obtainable from another string (s_2) if (s_1) can be derived from (s_2) by deleting some characters. For instance, (\texttt{abc}) can be obtained from (\texttt{ab\red{dbe}c}) by deleting the highlighted characters.

Now, you are given two strings (s_1) and (s_2) and two integers (n_1) and (n_2). These are used to construct two strings: (\textbf{str}_1 = [s_1, n_1]) and (\textbf{str}_2 = [s_2, n_2]). Your task is to determine the maximum integer (m) such that the string (\textbf{str} = [\textbf{str}_2, m]) can be obtained as a subsequence of (\textbf{str}_1).

inputFormat

The input consists of four lines:

1. The first line contains the string (s_1).
2. The second line contains the integer (n_1).
3. The third line contains the string (s_2).
4. The fourth line contains the integer (n_2).

outputFormat

Output a single integer representing the maximum integer (m) such that the string (\textbf{str} = [\textbf{str}_2, m]) can be obtained from (\textbf{str}_1).

sample

acb
4
ab
2

2