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