ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2118. Шифровка

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Штирлиц хочет передать очень важное сообщение s в штаб. Для этого он использует беспрефиксный код, зафиксированный по ГОСТ. К сожалению, противнику известен код, а канал связи Штирлица прослушивается. Чтобы отвести подозрения, Штирлиц хочет разбить шифровку на куски, каждый из которых нельзя расшифровать тем же кодом. Для максимальной безопасности Штирлиц хочет, чтобы количество кусков было максимально. Найдите максимальное количество кусков или определите, что разбить шифровку требуемым образом невозможно.

Исходные данные

В первой строке записано одно целое число k (1 ≤ k ≤ 52) — количество символов в алфавите. Символы пронумерованы от 1 до 52 в порядке A-Za-z, в тексте сообщения будут использованы только символы с номерами от 1 до k.
Во второй строке записана строка s длины до 106, состоящая из символов с номерами от 1 до k (нумерация символов определена выше).
В следующих k строках записаны двоичные коды символов алфавита согласно нумерации. Каждый символ алфавита кодируется последовательностью 0 и 1 длины не более k. Гарантируется, что никакой код не является префиксом другого кода.

Результат

Выведите одно число — максимальное количество кусков, либо -1, если разбить на куски указанным способом невозможно.

Примеры

исходные данныерезультат
3
CACB
011
1
001
2
3
ACBABCAACABCAACC
0
10
110
-1

Замечания

В первом семпле зашифрованный текст выглядит как 0010110011. Единственный способ разбить его на куски, которые нельзя расшифровать — 0 010110011. Следовательно, ответ равен 2.
Во втором семпле можно показать по индукции, что любая строчка, которая заканчивается на 0 и не содержит трёх 1 подряд, расшифровывается данным кодом. Любой суффикс зашифрованного текста имеет такой вид, поэтому ответ — -1.
Автор задачи: Алексей Данилюк
Источник задачи: Петрозаводск лето 2018. t.me/umnik_team Contest