Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Короче... (задача C II тура окружного этапа Всероссийской олимпиады школьников 2014 - 2015)

Задачу добавил: alef

Успешно сдано решений: 26

Ограничение по времени на тест 2 секунды
Ограничение по памяти на тест 256 мегабайт
ввод input.txt
вывод output.txt

Перун-Нечитайло теперь зарабатывает написанием рекламных текстов. Бывают люди, которые сначала пишут короткие тексты, а потом уже добавляют в них подробности. Бывают люди, которые сначала пишут пространные тексты, а потом их сокращают. Перун-Нечитайло относится ко второму типу, и иной раз ему приходится трудно, когда текст должен иметь длину не более заданного количества знаков.

Текст, который написал Галактион, содержит m знаков, и теперь журналисту требуется сократить текст так, чтобы он содержал не более n знаков. Перун-Нечитайло хотел бы удалить из текста как можно меньшее количество слов. Но есть одна тонкость: некоторые слова в тексте являются ключевыми, и эти слова удалять нельзя.

Ради простоты будем считать, что текст содержит только слова, состоящие из строчных латинских букв, и слова разделяются ровно одним пробелом. Пробелы учитываются при подсчёте символов. В полученном тексте слова также должны разделяться ровно одним пробелом. И исходный, и полученный текст не начинаются и не заканчиваются пробелом. Длина каждого слова не превосходит 20 символов.

Ваша задача — определить, какое минимальное количество слов придётся удалить Галактиону.

Входные данные

В первой строке содержатся целые числа m, n и k (1 ≤ n < m ≤ 104,  1 ≤ k ≤ 102) — количество символов в тексте Перуна-Нечитайло, требуемое количество символов в тексте и количество ключевых слов.

Далее следуют k строк, в каждой из которых записано по одному ключевому слову. Гарантируется, что все слова различны.

Далее следует текст Перуна-Нечитайло, начинающийся словом и заканчивающийся словом; все слова разделены не более чем одним пробелом.

Гарантируется, что длина любого из слов не превосходит 20 символов.

Выходные данные

В первой строке выведите единственное целое число — минимальное количество слов, которое придется удалить Перуну-Нечитайло.

Если текст сократить нельзя, выведите в качестве ответа  - 1.

Примеры тестов
Входные данные - 1
37 28 5
zadacha
e
ne
takaya
prostaya
to be or not to be this is a question
Выходные данные - 1
1
Входные данные - 2
37 27 5
ochevidnaya
ideya
ne
daet
ballov
to be or not to be this is a question
Выходные данные - 2
2
Входные данные - 3
37 28 4
spoilery
ne
horosho
question
to be or not to be this is a question
Выходные данные - 3
2
Входные данные - 4
37 36 8
to
be
or
not
this
is
a
question
to be or not to be this is a question
Выходные данные - 4
-1
Входные данные - 5
5 1 1
hello
world
Выходные данные - 5
1

Сдать задачу

Задать вопрос жюри по этой задаче