{"raw_statement":[{"iden":"statement","content":"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.\n\nScientists 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.\n\nScientists 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."},{"iden":"input","content":"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_.\n\nThe 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.\n\nThe 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.\n\nAll 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."},{"iden":"output","content":"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_."},{"iden":"examples","content":"Input\n\n5 3 13\nBACAC\n4 1 2\n1 2 3\n2 3 4\n3 4 10\n\nOutput\n\n5"},{"iden":"note","content":"Explanation: one can obtain the following organisms (risks are stated in brackets): BACAC (11), ACAC (10), BAA (5), B (6), AA (4)."}],"translated_statement":[{"iden":"statement","content":"奥米伽星球的科学家正在研究原始生物的突变。该星球生物的基因组可以用前 #cf_span[K] 个大写英文字母组成的字符串表示。对于每一对基因类型，他们分配了 #cf_span[ai, j] —— 表示当这两种基因在基因组中相邻时，生物患病的风险，其中 #cf_span[i] 是第一个基因的 1-索引，#cf_span[j] 是第二个基因的索引。基因 'A' 的索引为 1，'B' 的索引为 2，依此类推。例如，#cf_span[a3, 2] 表示片段 'CB' 的风险。生物患病的总风险等于基因组中每一对相邻基因的风险之和。\n\n科学家已经获得了一个基础生物。可以通过对该生物进行突变获得新的生物。突变过程包括移除所有某种特定类型的基因。这种移除会额外增加总患病风险。对于每种基因类型，科学家确定了 #cf_span[ti] —— 表示移除所有类型为第 #cf_span[i] 种的基因时，总患病风险的增加量。例如，#cf_span[t4] 表示移除所有 'D' 基因时额外增加的总风险值。\n\n科学家希望找出从给定生物中能够获得的、总患病风险不超过 #cf_span[T] 的不同生物的数量。他们只能使用上述的突变过程。两个生物被认为是不同的，当且仅当表示其基因组的字符串不同。基因组必须至少包含一个基因。\n\n输入的第一行包含三个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 200 000]) —— 基础生物基因组的长度，#cf_span[K] (#cf_span[1 ≤ K ≤ 22]) —— 基因组中基因类型的最大索引，以及 #cf_span[T] (#cf_span[1 ≤ T ≤ 2·109]) —— 允许的最大患病风险。第二行包含给定生物的基因组，它是一个由前 #cf_span[K] 个大写英文字母组成的、长度为 #cf_span[N] 的字符串。\n\n第三行包含 #cf_span[K] 个数字 #cf_span[t1, t2, ..., tK]，其中 #cf_span[ti] 表示移除所有第 #cf_span[i] 类型基因时额外增加的患病风险值。\n\n接下来的 #cf_span[K] 行包含矩阵 #cf_span[ai, j] 的元素。第 #cf_span[i] 行包含 #cf_span[K] 个数字，该行第 #cf_span[j] 个数字表示由第 #cf_span[i] 个字母和第 #cf_span[j] 个字母组成的基因对的患病风险。给定的矩阵 *不* 一定是对称的。\n\n输入中的所有数字均为非负整数，除 #cf_span[T] 外，所有数字均不超过 #cf_span[109]。保证从给定生物中可获得的生物的最大可能风险严格小于 #cf_span[231]。\n\n请输出能够从基础生物中获得且总患病风险不超过 #cf_span[T] 的生物数量。\n\n解释：可以得到以下生物（括号内为风险值）：BACAC (11), ACAC (10), BAA (5), B (6), AA (4)。"},{"iden":"input","content":"输入的第一行包含三个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 200 000]) —— 基础生物基因组的长度，#cf_span[K] (#cf_span[1 ≤ K ≤ 22]) —— 基因组中基因类型的最大索引，以及 #cf_span[T] (#cf_span[1 ≤ T ≤ 2·109]) —— 允许的最大患病风险。第二行包含给定生物的基因组，它是一个由前 #cf_span[K] 个大写英文字母组成的、长度为 #cf_span[N] 的字符串。第三行包含 #cf_span[K] 个数字 #cf_span[t1, t2, ..., tK]，其中 #cf_span[ti] 表示移除所有第 #cf_span[i] 类型基因时额外增加的患病风险值。接下来的 #cf_span[K] 行包含矩阵 #cf_span[ai, j] 的元素。第 #cf_span[i] 行包含 #cf_span[K] 个数字，该行第 #cf_span[j] 个数字表示由第 #cf_span[i] 个字母和第 #cf_span[j] 个字母组成的基因对的患病风险。给定的矩阵 *不* 一定是对称的。输入中的所有数字均为非负整数，除 #cf_span[T] 外，所有数字均不超过 #cf_span[109]。保证从给定生物中可获得的生物的最大可能风险严格小于 #cf_span[231]。"},{"iden":"output","content":"请输出能够从基础生物中获得且总患病风险不超过 #cf_span[T] 的生物数量。"},{"iden":"examples","content":"输入\n5 3 13\nBACAC\n4 1 2\n1 2 3\n2 3 4\n3 4 10\n输出\n5"},{"iden":"note","content":"解释：可以得到以下生物（括号内为风险值）：BACAC (11), ACAC (10), BAA (5), B (6), AA (4)。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the length of the base genome.  \nLet $ K \\in \\mathbb{Z}^+ $ ($1 \\leq K \\leq 22$) be the number of distinct gene types (labeled $1$ to $K$, corresponding to letters 'A' to the $K$-th letter).  \nLet $ T \\in \\mathbb{Z}^+ $ be the maximum allowable total risk.  \n\nLet $ G = g_1 g_2 \\dots g_N $ be the base genome, where each $ g_i \\in \\{1, 2, \\dots, K\\} $.  \n\nLet $ t = (t_1, t_2, \\dots, t_K) \\in \\mathbb{Z}_{\\geq 0}^K $, where $ t_i $ is the additional risk incurred by removing *all* genes of type $ i $.  \n\nLet $ A = (a_{i,j})_{K \\times K} \\in \\mathbb{Z}_{\\geq 0}^{K \\times K} $, where $ a_{i,j} $ is the risk contributed by adjacent pair $ (i, j) $ (gene of type $ i $ followed by gene of type $ j $).  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 200{,}000 $  \n2. $ 1 \\leq K \\leq 22 $  \n3. $ 1 \\leq T \\leq 2 \\cdot 10^9 $  \n4. $ 0 \\leq t_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, K\\} $  \n5. $ 0 \\leq a_{i,j} \\leq 10^9 $ for all $ i,j \\in \\{1, \\dots, K\\} $  \n6. The maximal possible risk over all obtainable organisms $ < 2^{31} $  \n\n**Objective**  \nAn organism is obtainable by *removing all genes of some subset* $ S \\subseteq \\{1, 2, \\dots, K\\} $, resulting in a subsequence of $ G $ consisting only of genes with types in $ \\overline{S} = \\{1, \\dots, K\\} \\setminus S $.  \n\nThe total risk of the resulting genome $ G' $ is:  \n$$\nR(S) = \\sum_{i \\in S} t_i + \\sum_{\\substack{1 \\leq \\ell < N \\\\ g_\\ell, g_{\\ell+1} \\in \\overline{S}}} a_{g_\\ell, g_{\\ell+1}}\n$$\n\nNote: The second sum is over adjacent pairs in the *remaining* genome (i.e., only those adjacent pairs where both genes are *not* removed).  \n\nWe require $ R(S) \\leq T $, and $ G' \\neq \\varepsilon $ (i.e., $ \\overline{S} \\neq \\emptyset $).  \n\nLet $ \\mathcal{S} = \\{ S \\subseteq \\{1, \\dots, K\\} \\mid \\overline{S} \\neq \\emptyset \\text{ and } R(S) \\leq T \\} $.  \n\n**Output**: $ |\\mathcal{S}| $, the number of such subsets $ S $.","simple_statement":null,"has_page_source":false}