C. Mutation
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

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 ai, 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, a3, 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 ti — the increasement of the total risk of disease occurence provided by removal of all genes having type with index i. For example, t4 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.

Input

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 t1, t2, ..., tK, where ti 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 ai, 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.

Output

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.

Examples
Input
5 3 13
BACAC
4 1 2
1 2 3
2 3 4
3 4 10
Output
5
Note

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