题目描述

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

称字符串 $a$ 能由字符串$b$生成，当且仅当从字符串 $b$中删除某些字符后可以得到字符串$a$。

例如 abdbec 可以生成 abc，但是 acbbe 不能生成 abc。

给定两个字符串 $s_1$ 和 $s_2$，以及两个整数$n_1$ 和$n_2$，求一个最大的整数 $m$，满足 $conn(conn(s_2,n_2),m)$能由 $conn(s_1,n_1)$生成。

输入格式

输入包含多组测试数据。

每组数据由 2 行组成，第一行包含 $s_2,n_2$，第二行包含 $s_1,n_1$。

输出格式

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

样例

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$不大于 $10^6$

来源

• 算法竞赛进阶指南