Stepan 有一组 n 个字符串。而且,他还有一个最喜欢的弦s。
Stepan 想要执行以下操作。他会拿出他那一套中的一些琴弦,然后将它们逐一写下来。有可能他会多次拿走一些绳子,也有可能根本不会拿走一些。
您的任务是确定 Stepan 需要获取和写入的集合中字符串的最小数量,以便字符串 s 作为结果写下的字符串中的子序列出现。
例如,在字符串“abcd”中,字符串“ad”、“acd”、“abcd”显示为子序列,字符串“ba”、“abdc”不显示为子序列。
输入
第一行包含整数 n (1 ≤ n ≤ 50) — Stepan 集合中的字符串数量。
接下来的 n 行包含 n 个由英文字母小写字母组成的非空字符串。每个字符串的长度不超过 50 个符号。 Stepan 的琴弦组中的某些琴弦可能是相同的。
下一行包含非空字符串 s,由英文字母表中的小写字母组成——Stepan 最喜欢的字符串。该字符串的长度不超过 2500 个符号。
输出
打印 Stepan 应该从集合中取出的最小字符串数,并将它们逐个写下来,以便字符串 s 作为结果写下的字符串中的子序列出现。该组中的每个字符串都应按照 Stepan 从该组中取出的次数进行计数。
如果答案不存在,则打印 -1。
示例
输入 #1
3 a aa a aaa
输出 #1
2
输入 #2
4 ab aab aa bb baaab
输出 #2
3
输入 #3
2 aaa bbb aaacbbb
输出 #3
-1
注意
在第一个测试中,Stepan 可以从该组中取出第三根和第二根弦,将它们写下来,并准确地得到他最喜欢的弦。
在第二个示例中,Stepan 可以从集合中取出第二个、第三个和第二个字符串,并将它们写下来。然后他会得到一个字符串“aabaaaab”,其中他最喜欢的字符串“baaab”是一个子序列。
在第三个测试中,Stepan 无法获得他最喜欢的字符串,因为它包含字母“c”,而该字符串中的任何字符串中都没有出现该字母。