Count the Repetitions
题号：NC51190
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

定义 conn(s,n)conn(s,n) 为 n 个字符串 s 首尾相接形成的字符串，例如：

conn(“abc”,2)=”abcabc”conn(“abc”,2)=”abcabc”

称字符串 a 能由字符串 b 生成，当且仅当从字符串 b 中删除某些字符后可以得到字符串 a。
例如“abdbec”可以生成“abc”，但是“acbbe”不能生成“abc”。
给定两个字符串 s1s1 和 s2s2，以及两个整数n_1 和 n_2，求一个最大的整数 m，满足conn(conn(s_2,n_2),m)能由 conn(s_1,n_1) 生成。


输入描述:

输入包含多组测试数据。
每组数据由2行组成，第一行包含s2,n2s2,n2，第二行包含s1,n1s1,n1。

输出描述:

对于每组数据输出一行表示答案m。
示例1

输入

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

输出

复制 
2
1
4
7
12

备注:

s_1和 s_2 长度不超过100，n_1 和n_2 不大于 。