Задача №111767. Мутация
Ученые планеты Олимпия проводят очередной эксперимент в области мутации примитивных организмов. Геном организма с этой планеты может быть представлен в виде строки из первых K заглавных букв английского алфавита. Для каждой пары типов генов было установлено риск возникновения заболевания, при условии что гены этих типов стоят подряд в геноме. Риск возникновения заболевания у организма равен сумме рисков для каждой пары соседних генов в геноме и измеряется он в рискограммах.
Ученые уже получили базовый организм, из которого путем мутации могут быть получены другие организмы. Механизм мутации включает удаление всех генов определенных типов. Такое удаление увеличивает риск возникновения заболевания, причем для каждого типа генов было определено, на сколько увеличится риск заболевания организма, если этот тип будет удален. Цель ученых — посчитать количество различных организмов, которые можно получить из базового описанным выше путем, причем риск возникновения заболевания у которых не превышает T рискограмм. Два организма считаются разными, если строки задающие их геномы отличаются. Геном полученного организма должен состоять хотя бы из одного гена.
Напишите программу, которая по информации о геноме базового организма и параметрам возникновения риска заболевания найдет количество различных организмов, которые можно получить из базового, таких, что риск возникновения заболевания не превышает T рискограмм.
Первая строка входного файла содержит 3 целых числа: N ( 1 ≤ N ≤ 200000 ) — длину генома начального организма, K ( 1 ≤ K ≤ 21 ) — количество различных букв, которые могут встречаться в геноме и T ( 1 ≤ T ≤ 10 9 ) — максимальный допустимый риск возникновения заболевания. Вторая строка содержит геном базового организма — строка длины N , состоящий только из первых K заглавных букв английского алфавита. Третья строка содержит K чисел, задающих риск возникновения заболевания при удалении всех генов определенного типа, причем i -ое число соответствует i-ой букве английского алфавита. Следующие K строк содержат по K чисел, причем j -ое число в строке с номером i из них задает риск возникновения заболевания для пары генов, первый из которых соответствует i-ой букве, а второй j -ой букве. Все числа во входном файле целые, неотрицательные и не превышают 10 9 . Все риски заданы в рискограммах. Гарантируется, что наибольший возможный риск заболевания организма, который может быть получен из исходного, строго меньше 2 31 .
Единственная строка выходного файла должна содержать одно целое число — искомое количество разных организмов с риском возникновения заболевания не более T рискограммов, которые могут быть получены из базового путем описанным в условии.
Возможно получить такие организмы (в скобках указано риски): BACAC (11), ACAC (10), BAA (5), B (6), AA (4).
5 3 13 BACAC 4 1 2 1 2 3 2 3 4 3 4 10
5