Мутація#2011
Вчені на планеті Олімпія проводять експеримент над мутацією примітивних організмів. Геном організму з цієї планети можна представити у вигляді рядка, складеного з перших великих літер англійського алфавіту. Для кожної пари типів генів визначено ризик виникнення хвороби, коли ці типи знаходяться поруч у геномі. Загальний ризик хвороби для організму — це сума ризиків для кожної пари сусідніх генів у геномі, вимірюється у ризикограмах.
Вчені отримали базовий організм, з якого шляхом мутації можна отримати інші організми. Ця мутація полягає у видаленні всіх генів певних типів. Таке видалення підвищує ризик хвороби, і для кожного типу гена вказано збільшення ризику хвороби при його видаленні. Вчені прагнуть визначити кількість різних організмів, які можна отримати з базового організму цим методом, за умови, що ризик хвороби не перевищує ризикограм. Два організми вважаються різними, якщо їхні геноми відрізняються. Геном отриманого організму має містити хоча б один ген.
Напишіть програму, яка за заданим геномом базового організму та параметрами виникнення ризику хвороби визначає кількість різних організмів, які можна отримати з базового так, щоб ризик хвороби не перевищував ризикограм.
У першому рядку містяться числа: (1 \leq N \leq 200\,000) — довжина геному базового організму, (1 \leq K \leq 21) — кількість різних літер, які можуть зустрічатись у геномі, і (1 \leq T \leq 10^9) — максимально дозволений ризик хвороби.
У другому рядку задано геном базового організму — рядок довжини , що складається лише з перших великих літер англійського алфавіту.
У третьому рядку містяться цілих чисел, де -те число вказує збільшення ризику хвороби при видаленні всіх генів -ї літери.
Наступні рядків містять по цілих чисел, де число у -му рядку і -му стовпчику вказує ризик хвороби для пари генів, де перший — -та літера, а другий — -та літера.
Всі вхідні числа — невід’ємні цілі числа, що не перевищують 10^9. Всі ризики вказано у ризикограмах. Гарантується, що максимальний можливий ризик хвороби будь-якого організму, який можна отримати з базового, строго менший за 2^{31}.
Виведіть одне ціле число — кількість різних організмів із ризиком хвороби не більше ризикограм, які можна отримати з базового організму описаним способом.
Приклад 1