Короче... (задача C II тура окружного этапа Всероссийской олимпиады школьников 2014 - 2015)
Задачу добавил: alef
Успешно сдано решений: 27
Перун-Нечитайло теперь зарабатывает написанием рекламных текстов. Бывают люди, которые сначала пишут короткие тексты, а потом уже добавляют в них подробности. Бывают люди, которые сначала пишут пространные тексты, а потом их сокращают. Перун-Нечитайло относится ко второму типу, и иной раз ему приходится трудно, когда текст должен иметь длину не более заданного количества знаков.
Текст, который написал Галактион, содержит m знаков, и теперь журналисту требуется сократить текст так, чтобы он содержал не более n знаков. Перун-Нечитайло хотел бы удалить из текста как можно меньшее количество слов. Но есть одна тонкость: некоторые слова в тексте являются ключевыми, и эти слова удалять нельзя.
Ради простоты будем считать, что текст содержит только слова, состоящие из строчных латинских букв, и слова разделяются ровно одним пробелом. Пробелы учитываются при подсчёте символов. В полученном тексте слова также должны разделяться ровно одним пробелом. И исходный, и полученный текст не начинаются и не заканчиваются пробелом. Длина каждого слова не превосходит 20 символов.
Ваша задача — определить, какое минимальное количество слов придётся удалить Галактиону.
В первой строке содержатся целые числа m, n и k (1 ≤ n < m ≤ 104, 1 ≤ k ≤ 102) — количество символов в тексте Перуна-Нечитайло, требуемое количество символов в тексте и количество ключевых слов.
Далее следуют k строк, в каждой из которых записано по одному ключевому слову. Гарантируется, что все слова различны.
Далее следует текст Перуна-Нечитайло, начинающийся словом и заканчивающийся словом; все слова разделены не более чем одним пробелом.
Гарантируется, что длина любого из слов не превосходит 20 символов.
В первой строке выведите единственное целое число — минимальное количество слов, которое придется удалить Перуну-Нечитайло.
Если текст сократить нельзя, выведите в качестве ответа - 1.
37 28 5
zadacha
e
ne
takaya
prostaya
to be or not to be this is a question
1
37 27 5
ochevidnaya
ideya
ne
daet
ballov
to be or not to be this is a question
2
37 28 4
spoilery
ne
horosho
question
to be or not to be this is a question
2
37 36 8
to
be
or
not
this
is
a
question
to be or not to be this is a question
-1
5 1 1
hello
world
1