奥林匹亚星球的科学家正在进行一项原始生物突变实验。这个星球上的生物体基因组可以用前K个大写英文字母组成的字符串来表示。对于每一对类型的基因,他们分配了 ai、j——生物体中发生疾病的风险,前提是这些类型的基因在基因组中相邻,其中 i——第一个基因的基于 1 的索引,j——第二个基因的索引。基因“A”的索引为 1,“B”的索引为 2,依此类推。例如,a3,2代表“CB”片段的风险。生物体发生疾病的风险等于基因组中每对相邻基因的风险之和。
科学家已经获得了基础生物。通过对这种生物体进行变异,可以获得一些新的生物体。突变涉及去除某些特定类型的所有基因。这种去除另外增加了疾病发生的总风险。对于每种类型的基因,科学家们确定了 ti——通过去除具有指数 i 的类型的所有基因而导致的疾病发生总风险的增加。例如,t4代表在去除所有“D”基因的情况下额外总风险增加的值。
科学家想要从给定的生物体中找到许多不同的生物体,其疾病发生的总风险不大于T。他们只能使用上述的突变过程。如果代表两个生物体基因组的字符串不同,则认为它们不同。基因组应至少包含一个基因。
输入
输入的第一行包含三个整数 N (1 ≤ N ≤ 200 000) — 基础生物体的基因组长度,K (1 ≤ K ≤ 22) — 基因组中基因类型的最大索引,T (1 ≤ T ≤ 2·109) — 疾病发生的最大允许风险。第二行包含给定生物体的基因组。它是由前K个大写英文字母组成的字符串,长度为N。
第三行包含K个数字t1,t2,...,tK,其中ti是通过去除第i种类型的所有基因而提供的疾病发生的附加风险值。
接下来的 K 行包含给定矩阵 ai, j 的元素。第 i 行包含 K 个数字。第i行的第j个数字代表这对基因发生疾病的风险,第一个对应于第i个字母,第二个对应于第j个字母。给定的矩阵不一定是对称的。
输入中的所有数字都是整数、非负数,并且除 T 之外的所有数字均不大于 109。保证从给定生物体中可以获得的生物体的最大可能风险严格小于 231。
输出
输出从基数1中可以获得的、疾病发生总风险不大于T的生物体的数量。
示例
输入 #1
5 3 13 BACAC 4 1 2 1 2 3 2 3 4 3 4 10
输出 #1
5
注意
说明:可获得以下生物体(括号内注明风险):BACAC(11)、ACAC(10)、BAA(5)、B(6)、AA(4)。