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

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

Во второй строке записана строка s длины до 10⁶, состоящая из символов с номерами от 1 до k (нумерация символов определена выше).

В следующих k строках записаны двоичные коды символов алфавита согласно нумерации. Каждый символ алфавита кодируется последовательностью 0 и 1 длины не более k. Гарантируется, что никакой код не является префиксом другого кода.

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

В первом семпле зашифрованный текст выглядит как 0010110011. Единственный способ разбить его на куски, которые нельзя расшифровать — 0 010110011. Следовательно, ответ равен 2.

Во втором семпле можно показать по индукции, что любая строчка, которая заканчивается на 0 и не содержит трёх 1 подряд, расшифровывается данным кодом. Любой суффикс зашифрованного текста имеет такой вид, поэтому ответ — -1.