- Финальный
- Отборочный
- 3-й квал
- 2-й квал
- 1-й квал
- Разогревочный
Отборочный раунд завершен
Задания
Показывать по одной задаче на странице / все задачи на одной странице
"B" Новая клавиатура
| Ограничение по времени | 2 секунды |
|---|---|
| Ограничение по памяти | 256 мегабайт |
Петя купил новую клавиатуру. Она поддерживает n раскладок. В каждой раскладке можно набирать некоторое подмножество строчных букв латинского алфавита. Пронумеруем раскладки от 1 до n.
Петя хочет набрать некоторое сообщение, состоящее из m строчных букв латинского алфавита. Исходно активна первая раскладка. Петя может производить следующие действия:
- Переключить раскладку. Тогда, если текущая раскладка имела номер i, новая раскладка будет иметь номер i mod n + 1, где mod — операция взятия остатка по модулю. Если предыдущим действием Петя также переключал раскладку, это действие займет b миллисекунд, иначе это действие займет a миллисекунд.
- Набрать символ. Петя может добавить в конец текущего сообщения любую букву, содержащуюся в текущей раскладке. На это действие он потратит c миллисекунд.
Помогите Пете определить минимальное время, необходимое, чтобы набрать сообщение, либо выясните, что набрать сообщение невозможно. Раскладка, которая останется включенной после набора сообщения, может быть любой.
| Формат входных данных |
В первой строке содержатся четыре целых числа n, a, b и c — количество раскладок у клавиатуры, и количество миллисекунд, необходимых для совершения переключения раскладки и набора символа (1 ≤ n ≤ 2 000, 1 ≤ b ≤ a ≤ 109, 1 ≤ c ≤ 109). В следующих n строках содержится описание раскладок. Каждая раскладка описывается непустой строкой, в которой каждая строчная буква латинского алфавита встречается не более одного раза — подмножество букв, которые можно набрать в этой раскладке. Буквы в этой строке упорядочены в алфавитном порядке. В последней строке содержится строка s — сообщение, которое хочет набрать Петя (длина строки s от 1 до 2 000). Строка s состоит из строчных латинских букв. |
|---|---|
| Формат выходных данных |
Выведите единственное целое число — минимальное количество миллисекунд, необходимое, чтобы набрать сообщение. Выведите - 1, если набрать сообщение невозможно. |
| Примеры |
Входные данные
5 3 2 1 abc d e f def abcdef
Выходные данные
15 |
|
Входные данные
1 1 1 1 a z
Выходные данные
-1 |
|
|
|