eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Мутация

Мутация

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Учёные планеты Олимпия проводят очередной эксперимент в области мутации примитивных организмов. Геном организма с этой планети может быть представлен в виде строки из первых K заглавных букв английского алфавита. Для каждой пары типов генов был установлен риск возникновения заболевания, при условии что гены этих типов стоят подряд в геноме. Риск возникновения заболевания в организме равен сумме рисков для каждой пары соседних генов в геноме и измеряется он в рискограммах.

Ученые уже получили базовый организм, из которого путём мутации могут быть получены другие организмы. Механизм мутации включает в себя удаление всех генов определённых типов. Такое удаление увеличивает риск возникновеия заболевания, причём для каждого типа генов было определено, на сколько увеличится риск заболевания организма, если этот тип будет удалён. Мета учёных – посчитать количество разных организмов, которые можно получить из базового описанным выше путём, причём риск возниникновения заболевания в которых не превышает T рискограмм. Два организма считаются разными, если строки, задающие их геномы, отличаются. Геном полученного организма должен состоять хотя бы из одного гена.

Напишите программу, которая по информации о геноме базового организма и параметрам возникновения риска заболевания найдёт количество разных организмов, которые можно получить из базового, таких, что риск возникновения заболевания не превышает T рискограмм.

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

Первая строка содержит 3 целих числа: N (1 N 200 000) - длину генома начального организма, K (1 K 21) - количество разных букв, которые могут встречатся в геноме и T (1 T 10^9) - максимальный допустимый риск возникновения заболевания. Вторая строка содержит геном базового организма – строку длины N, состоящую только из первых K заглавных букв английского алфавита. Третья строка содержит K чисел, задающих риск возникновения заболевания при удалении всех генов определённого типа, причём i-тое число соответствует і-ой букве английского алфавита. Последующие K строк содержат по K чисел, причём j-тое число в строке с номером i из них задаёт риск возникновения заболевания для пары генов, первый из которых соответствует i-ой букве, а второй - j-ой букве. Все входные числа целые, неотрицательные и не превышают 10^9. Все риски заданы в рискограммах. Гарантируется, что наибольший возможный риск заболевания организма, который может быть получен из начального, строго меньший за 2^31.

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

Вывести одно целое число - искомое количество разных организмов с риском возникновения заболевания не более T рискограмм, которые могут быть получены из базового описанным в условии путём.

Пример

Входные данные #1
5 3 13
BACAC
4 1 2
1 2 3
2 3 4
3 4 10
Выходные данные #1
5
Автор Ярослав Твердохлеб
Источник 2011 XXIV Всеукраинская олимпиада по информатике, Черкассы, Март 26 - 31, тур 2