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.

N/A

N/A

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