Mutation
Scientists on the planet Olympia are conducting an experiment on the mutation of primitive organisms. The genome of an organism on this planet can be represented as a string composed of the first K capital letters of the English alphabet. For each pair of gene types, the risk of disease occurrence has been determined when these genes are adjacent in the genome. The total disease risk for an organism is the sum of the risks for each pair of neighboring genes in the genome, measured in riskograms.
The scientists have a base organism from which other organisms can be derived through mutation. This mutation involves removing all genes of certain types. Such removal increases the disease risk, and for each gene type, the increase in risk when that type is removed has been specified. The scientists aim to calculate the number of distinct organisms that can be derived from the base organism using this method, ensuring that the disease risk does not exceed T riskograms. Two organisms are considered distinct if their genome strings differ. The resulting organism's genome must contain at least one gene.
Write a program that, given the genome of the base organism and the parameters for disease risk occurrence, determines the number of distinct organisms that can be derived from the base organism with a disease risk not exceeding T riskograms.
Input
The first line contains 3 integers: N (1 ≤ N ≤ 200,000) - the length of the genome of the initial organism, K (1 ≤ K ≤ 21) - the number of different letters that can appear in the genome, and T (1 ≤ T ≤ 10^9) - the maximum allowable disease risk. The second line contains the genome of the base organism - a string of length N, consisting only of the first K capital letters of the English alphabet. The third line contains K numbers, each representing the increase in disease risk when all genes of a certain type are removed, with the i-th number corresponding to the i-th letter of the English alphabet. The next K lines each contain K numbers, where the j-th number in the i-th line specifies the disease risk for a pair of genes, the first of which corresponds to the i-th letter, and the second to the j-th letter. All input numbers are integers, non-negative, and do not exceed 10^9. All risks are given in riskograms. It is guaranteed that the maximum possible disease risk of an organism derived from the initial one is strictly less than 2^31.
Output
Output a single integer - the number of distinct organisms with a disease risk not exceeding T riskograms that can be derived from the base organism using the described method.