Mutation#2011
Scientists on the planet Olympia are conducting an experiment on the mutation of primitive organisms. The genome of an organism from this planet can be represented as a string composed of the first capital letters of the English alphabet. For each pair of gene types, the risk of disease occurrence has been determined when these types are adjacent in the genome. The total disease risk for an organism is the sum of the risks for each pair of neighboring gene types in the genome, measured in riskograms.
The scientists have obtained 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 disease risk when that type is removed has been specified. The scientists aim to determine the number of distinct organisms that can be obtained from the base organism by this method, with the condition that the disease risk does not exceed 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, finds the number of distinct organisms that can be obtained from the base organism so that the disease risk does not exceed riskograms.
The first line contains integers: (1 \leq N \leq 200\,000) — the length of the base organism's genome, (1 \leq K \leq 21) — the number of different letters that can appear in the genome, and (1 \leq T \leq 10^9) — the maximum allowable disease risk.
The second line contains the genome of the base organism — a string of length , consisting only of the first capital letters of the English alphabet.
The third line contains integers, where the -th number specifies the increase in disease risk when all genes of the -th letter are removed.
The next lines each contains integers, where the number in the -th row and -th column specifies the disease risk for a pair of genes where the first is the -th letter and the second is the -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 any organism that can be derived from the base one is strictly less than 2^{31}.
Output a single integer — the number of distinct organisms with a disease risk not exceeding riskograms that can be obtained from the base organism using the described method.
Example 1