CF76C.Mutation

Scientists of planet Olympia are conducting an experiment in mutation of primitive organisms. Genome of organism from this planet can be represented as a string of the first K capital English letters. For each pair of types of genes they assigned a__i, j — a risk of disease occurence in the organism provided that genes of these types are adjacent in the genome, where i — the 1-based index of the first gene and j — the index of the second gene. The gene 'A' has index 1, 'B' has index 2 and so on. For example, _a_3, 2 stands for the risk of 'CB' fragment. Risk of disease occurence in the organism is equal to the sum of risks for each pair of adjacent genes in the genome.

Scientists have already obtained a base organism. Some new organisms can be obtained by mutation of this organism. Mutation involves removal of all genes of some particular types. Such removal increases the total risk of disease occurence additionally. For each type of genes scientists determined t__i — the increasement of the total risk of disease occurence provided by removal of all genes having type with index i. For example, _t_4 stands for the value of additional total risk increasement in case of removing all the 'D' genes.

Scientists want to find a number of different organisms that can be obtained from the given one which have the total risk of disease occurence not greater than T. They can use only the process of mutation described above. Two organisms are considered different if strings representing their genomes are different. Genome should contain at least one gene.

奥林匹亚星球的科学家们正在对原始生物进行突变实验。该星球上生物的基因组可表示为前 $K$ 个大写英文字母组成的字符串。对于每一对基因类型，科学家们定义了 $a_{i,j}$ —— 当这两种类型的基因在基因组中相邻时，该生物患病的风险值，其中 $i$ 表示第一个基因的 1-起始索引，$j$ 表示第二个基因的索引；字母 'A' 的索引为 1，'B' 的索引为 2，依此类推。例如，$a_{3,2}$ 表示基因片段 'CB' 所对应的风险值。整个生物的患病风险等于其基因组中所有相邻基因对所对应风险值之和。

科学家已获得一个基础生物体。若干新生物体可通过该基础生物体的突变获得。突变操作包括：移除某一特定类型的所有基因。这种移除操作还会额外增加总患病风险。针对每种基因类型，科学家确定了 $t_i$ —— 移除所有索引为 $i$ 的基因类型所导致的总患病风险的额外增量。例如，$t_4$ 表示移除所有 'D' 基因时所引入的额外总风险增量。

科学家希望找出：从给定的基础生物体出发，通过上述突变操作所能得到的、总患病风险 不超过 $T$ 的不同生物体的数目。两个生物体被视为不同，当且仅当它们的基因组字符串不同。基因组中必须至少包含一个基因。

The first line of the input contains three integer numbers N (1 ≤ N ≤ 200 000) — length of the genome of base organism, K (1 ≤ K ≤ 22) — the maximal index of gene type in the genome and T (1 ≤ T ≤ 2·109) — maximal allowable risk of disease occurence. The second line contains the genome of the given organism. It is a string of the first K capital English letters having length N.

The third line contains K numbers _t_1, _t_2, ..., t__K, where t__i is additional risk value of disease occurence provided by removing of all genes of the i-th type.

The following K lines contain the elements of the given matrix a__i, j. The i-th line contains K numbers. The j-th number of the i-th line stands for a risk of disease occurence for the pair of genes, first of which corresponds to the i-th letter and second of which corresponds to the j-th letter. The given matrix is not necessarily symmetrical.

All the numbers in the input are integer, non-negative and all of them except T are not greater than 109. It is guaranteed that the maximal possible risk of organism that can be obtained from the given organism is strictly smaller than 231.

输入的第一行包含三个整数 $N$（$1 \leq N \leq 200\,000$）——基础生物基因组的长度，$K$（$1 \leq K \leq 22$）——基因类型的最大编号，以及 $T$（$1 \leq T \leq 2\cdot10^9$）——允许的最大疾病发生风险。
第二行包含给定生物的基因组，它是一个长度为 $N$ 的字符串，由前 $K$ 个大写英文字母组成。

第三行包含 $K$ 个数 $t_1,\,t_2,\,\dots,\,t_K$，其中 $t_i$ 表示移除所有第 $i$ 类基因所额外引入的疾病发生风险值。

接下来的 $K$ 行描述给定的矩阵 $a_{i,j}$。第 $i$ 行包含 $K$ 个数，其中第 $i$ 行的第 $j$ 个数表示一对基因（第一个对应第 $i$ 个字母、第二个对应第 $j$ 个字母）所导致的疾病发生风险。该矩阵不一定对称。

输入中所有数字均为非负整数，且除 $T$ 外均不超过 $10^9$。保证由给定生物所能获得的最大可能风险严格小于 $2^{31}$。

Output the number of organisms that can be obtained from the base one and which have the total risk of disease occurence not greater than T.

输出可以从基础生物体获得、且疾病发生总风险不超过 T 的生物体数量。

Explanation: one can obtain the following organisms (risks are stated in brackets): BACAC (11), ACAC (10), BAA (5), B (6), AA (4).

解释：可以得到以下生物体（括号中为对应风险值）：BACAC（11）、ACAC（10）、BAA（5）、B（6）、AA（4）。