Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2018
The ABCD Murderer
abcd.c, abcd.cpp, Abcd.java, abcd.py
Oscar enjoys watching crime movies very much. He admires all those villains for how creative
some of them can get. He would like to show off some of his creativity, too. Sadly, he's quite
inexperienced and he is unable to come up with his own kind of a trick. So he would like to
get inspired by some old trick. He always loved watching criminals cutting out the letters from
newspapers and putting them together to form a ransom text. However, Oscar ain't a total rip
off so he came up with his own variant of this trick. He feels that putting the text together
letter by letter is simply too boring and time consuming. So he decided to create his ransom
note by cutting out whole words.
Oscar bought several mainstream newspapers, therefore he has practically unlimited source of
paper to cut the words from. He can cut out any particular word as many times as he wishes.
However, he's still limited by the set of words which appear in the newspapers. The trouble is
that some words are just not used in the newspapers at all. To make his job a bit easier, he
decided to erase all punctuation and all whitespace characters from the ransom note and ignore
the case of characters. He also allows the cut-out words to overlap, as far as the overlapping
parts contain the same text. Oscar now wonders how many words at minimum he has to cut
out from the newspapers to put together the ransom note.
Input Specification
The first input line contains an integer L (1 ≤ L ≤ 3 · 105), the number of words found in the
newspapers. The next line contains the text of the ransom note. The text is not empty and
consists of lowercase English letters only. It is at most 3 · 105 characters long.
Each of the next L lines contains one word appearing in the newspapers, in lowercase English
letters. None of these words is empty or longer than the text of the ransom note. All words
appearing in the newspapers are listed in the input at least once. Sum of lengths of all words is
not greater than 3 · 105 .
Output Specification
Output the minimal number of words Oscar has to cut out from the newspapers to compose his
ransom note. If it is not possible to compose the ransom note, print -1. Each word has to be
counted as many times as it is physically cut out from a newspaper.
Output for Sample Input 1
Sample Input 1
2
3
aaaaa
a
aa
aaa
Sample Input 2
Output for Sample Input 2
5
5
abecedadabra
abec
ab
ceda
dad
ra
Sample Input 3
Output for Sample Input 3
9
3
icpcontesticpc
international
collegiate
programming
contest
central
europe
regional
contest
icpc
