CF314B Sereja and Periods

设$[s,t]$（$s$为一个字符串，$t$为正整数）为字符串$s$重复$t$次后的新字符串 再设当字符串$s$中删去部分字符后，得到字符串$t$，则称字符串$s$包含$t$ 现在Sereja有两个字符串，可以表示为$w=[a,b]$和$q=[c,d]$，求使得$w$包含$[q,p]$的最大的正整数$p$

第一行为两个正整数$b,d$，其中$1\le b,d\le 10^7$ 第二行和第三行方便为字符串$a$和字符串$c$，其中$0

输出唯一一个整数$p$，为求使得$[a,b]$包含$[[c,d],p]$的最大的正整数$p$ 此外，如果没有合法的$p$，请输出$0$