[CERC2018] The ABCD Murderer

题目描述

**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [The ABCD Murderer](https://contest.felk.cvut.cz/18cerc/solved/abcd.pdf)** Oscar 特别喜欢看犯罪电影。他钦佩那些罪犯,因为他们富有创造力。他也想展示他的创造力。但很可惜的是,他没什么经验,也想不出来什么原创伎俩。所以他想从已有的招数中寻找灵感。他一直喜欢看罪犯从报纸上剪下字母,然后用这些字母拼勒索信的桥段。然而 Oscar 根本不想抄袭,所以他自己想了一个这种方法的变体。他觉得把字母一个一个拼成文本既无聊又费时间。所以他决定通过剪下一整个单词的方式拼出自己的勒索信。 Oscar 买来一些主流报纸,这样他几乎就有了无限的单词库。他可以多次剪出任意特定的单词。然而,他还是被报纸中出现的的单词集限制。问题是一些单词根本没在报纸中出现。为了让这项工作更简单,他决定去除勒索信中所有的标点符号和空格并且忽略字母的大小写。他同时允许剪出的单词互相重叠,只需要重叠部分相同。现在 Oscar 想知道他至少要剪下多少次单词才能拼成他想要的勒索信。

输入输出格式

输入格式


第一行包含一个整数 $L$,表示在报纸中发现的单词数; 下一行包含勒索信的内容 $s$。保证内容非空并且只包含小写英文字母。 接下来 $L$ 行,每行包含一个在报纸中出现的单词 $a_i$,保证只出现小写英文字母。这些单词中没有空串,也没有比勒索信长的单词。所有报纸中单词在输入中出现至少一次。

输出格式


输出 Oscar 最少要从报纸中剪下多少次单词才能组成勒索信、如果不能组成,输出 $-1$ 。每个单词都要被记实际从报纸剪下那么多次。

输入输出样例

输入样例 #1

3
aaaaa
a
aa
aaa

输出样例 #1

2

输入样例 #2

5
abecedadabra
abec
ab
ceda
dad
ra

输出样例 #2

5

输入样例 #3

9
icpcontesticpc
international
collegiate
programming
contest
central
europe
regional
contest
icpc

输出样例 #3

3

说明

$1≤L,|s|,∑|a_i|≤3×10^5$