#6547. 「CERC2018」The ABCD Murderer

内存限制:1024 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

译自 CERC 2018A. The ABCD Murderer

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\le L,|s|,\sum |a_i|\le 3\times 10^5