Олимпиадный тренинг

Задача . C. Мутация

Задача

Ученые планеты Олимпия проводят очередной эксперимент в области мутации примитивных организмов. Геном организма с этой планеты может быть представлен в виде строки из первых K заглавных букв английского алфавита. Для каждой пары типов генов было установлено риск возникновения заболевания a_i, j, при условии что гены этих типов стоят подряд в геноме, где i — номер первого гена (нумерация начинается с 1), j — номер второго гена. Ген 'A' имеет номер 1, 'B' имеет номер 2 и так далее. Например, a_3, 2 отвечает за пару 'CB'. Риск возникновения заболевания у организма равен сумме рисков для каждой пары соседних генов в геноме и измеряется он в рискограммах.

Ученые уже получили базовый организм, из которого путем мутации могут быть получены другие организмы. Механизм мутации включает удаление всех генов определенных типов. Такое удаление дополнительно увеличивает риск возникновения заболевания, причем для каждого типа генов было определено число t_i — на сколько увеличится риск заболевания организма, если все гены типа i будут удалены. Например, t₄ отвечает за суммарный риск, добавляющийся при удалении всех генов типа 'D'.

Цель ученых — посчитать количество различных организмов, которые можно получить из базового описанным выше путем, причем риск возникновения заболевания у которых не превышает T рискограмм. Два организма считаются разными, если строки задающие их геномы отличаются. Геном полученного организма должен состоять хотя бы из одного гена.

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

Первая строка входного файла содержит 3 целых числа: N (1 ≤ N ≤ 200000) — длину генома начального организма, K (1 ≤ K ≤ 22) — максимальный номер буквы, которая может встречаться в геноме и T (1 ≤ T ≤ 2·10⁹) — максимальный допустимый риск возникновения заболевания. Вторая строка содержит геном базового организма — строку длины N, состоящий только из первых K заглавных букв английского алфавита.

Третья строка содержит K чисел, t₁, t₂, ..., t_K, где t_i — дополнительное значение риска, которое добавляется при удалении всех генов типа i.

Следующие K строк содержат матрицу a_i, j. i-я строка содержит K чисел.j-ое число в строке с номером i задает риск возникновения заболевания для пары генов, первый из которых соответствует i-ой букве, а второй — j-ой букве.

Все числа во входном файле целые, неотрицательные и все кроме T не превышают 10⁹. Все риски заданы в рискограммах. Гарантируется, что наибольший возможный риск заболевания организма, который может быть получен из исходного, строго меньше 2³¹.

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

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

Примечание

Объяснение: возможно получить такие организмы (в скобках указано риски): BACAC (11), ACAC (10), BAA (5), B (6), AA (4).

Примеры

№	Входные данные	Выходные данные
1	5 3 13 BACAC 4 1 2 1 2 3 2 3 4 3 4 10	5

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет