题目描述

定义 $str = [s, n]$ 表示 $str$ 由 $n$ 个字符串 $s$ 连接构成。

例如，$str == [\texttt{abc}, 3] == \texttt{abcabcabc}$。 如果可以从 $s_2$ 中删除某些字符使其变为 $s_1$，则称字符串 $s_1$ 可以从字符串 $s_2$ 获得。

例如，根据定义，$s1 = abc$ 可以从 $s2 = abdbec$ 获得，仅需要删除$dbe$。

现在给你两个字符串 $s_1$ 和 $s_2$ 和两个整数 $n_1$ 和 $n_2$。由此构造得到两个字符串，其中 $str_1 = [s_1, n_1]$、$str_2 = [s_2, n_2]$。

请你找出一个最大整数 $m$，以满足 $str = [str_2, m]$ 可以从 $str_1$ 获得。

输入格式

本题有多组测试数据。测试数据不超过 $100$ 组。

对于每组测试数据，分为两行：

• 第一行输入字符串 $s_2$ 和整数 $n_2$；
• 第二行输入字符串 $s_1$ 和整数 $n_1$；

输出格式

对于每组测试数据，输出整数 $m$ 表示答案。

输入输出样例 #1

输入 #1

ab 2
acb 4
acb 1
acb 1
aa 1
aaa 3
baab 1
baba 11
aaaaa 1
aaa 20

输出 #1

2
1
4
7
12

说明/提示

数据保证，$s_1,s_2$ 全为小写字母构成，且 $1\leq |s_1|,|s_2| \leq 100$，$0\leq n_1,n_2\leq 10^6$，每个测试点的测试数据不超过 $100$ 组。