[ABC346] F - SSttrriinngg in StringString

F - SSttrriinngg in StringString

Time Limit: 3 sec / Memory Limit: 1024 MB

题面

对于长度为的字符串，记为重复次字符串得到的新字符串，记为按顺序重复次中的第一个字符、第二个字符，直至第个字符得到的新字符串。例如，如果 abc，那么 abcabc， aaabbbccc。同时，对于任意字符串，和都是空字符串。

给定一个正整数以及字符串和。找到最大的非负整数，使得是的一个（不一定连续）子序列。注意，根据定义，始终是的一个子序列。

什么是子序列？一个字符串的子序列是通过从中移除零个或多个字符，然后按原有顺序连接剩下的元素而得到的字符串。例如，ac、atcoder和空字符串是atcoder的子序列，但ta不是。

限制条件

• 是一个整数。
• 和是由小写英文字母组成且长度在到之间，包括边界值。

输入

输入以以下格式给出：

输出

输出最大的非负整数，使得是的一个（不一定连续）子序列。

输入样例 1

3
abc
ab

输出样例 1

2

我们有 abcabcabc。 aabb 是的一个子序列，但 aaabbb 不是，因此输出。

输入样例 2

3
abc
arc

输出样例 2

0

输入样例 3

1000000000000
kzazkakxkk
azakxk

输出样例 3

344827586207