Description

Lavish Circle（LC）是小镇住宅区内一条时尚的环形大道。LC 上的房屋价格极其昂贵，其中有些房屋目前还空着。LC 受到镇上黑手党的严密控制，他们希望用忠于黑手党的新房主填满这些空房。当 LC 完全住满后，每位房主将居住在 LC 上的一间房屋中。LC 是一条环形大道，房屋编号从 $1$ 到 $N$，即对于 $i < N$，第 $i$ 号房屋和第 $i+1$ 号房屋相邻，同时第 $N$ 号房屋和第 $1$ 号房屋也相邻。

房主（包括现有的和新入住的）根据他们每月能为黑手党支付保护费的金额被分为若干类别。这笔钱被称为 pizzo，通常由一名称为 pizzo 收集员（PC）的人收取。黑手党雇佣了一批这样的收集员。

PC 的工作是每月沿 LC 环形大道完整走一圈，并在途中从选定的房屋收取 pizzo。一次 PC 的收集路线上的所有被选中的房屋，其房主必须属于同一 pizzo 类别。收集路线必须从某一房屋出发并最终回到该房屋，以此检查 PC 是否正确完成了路线。在收集过程中，PC 每次都向前移动固定数量的房屋，直到再次回到起点。也就是说，PC 每次跳过的房屋数是一个非负整数 $d$，在整个收集过程中保持不变。必须满足 $(d+1)$ 能整除 $N$。

黑手党希望雇佣尽可能多的 PC。当然，雇佣多个 PC 意味着某些房主可能每月要多次支付 pizzo，但黑手党对此并不在意……然而，事情有个复杂之处。PC 们本是和平公民，通常不会互相开枪。但如果两名 PC 发现他们各自的收集路线访问了同一组房屋（无论访问顺序如何），他们就会互相开枪，从而引来警察，这种情况黑手党无论如何都要避免。因此，任何可能互相开枪的收集员不能同时被雇佣。

所有收集到的 pizzo 总价值还取决于新入住房主的类别。黑手党可以决定每个新房主的 pizzo 类别。显然，黑手党希望最大化他们的收入。你被雇佣为分析师，需要找出在 LC 完全且合理住满时，一个月内所有收集到的 pizzo 的最大可能总价值。黑手党将根据你的建议决定每个新房主的 pizzo 类别。LC 上的房屋数量 $N$ 是某个质数 $p$ 的非负整数次幂。

Input Format

第一行包含整数 $N$（$1 \leq N \leq 10^5$），$N$ 是某个质数 $p$ 的非负整数次幂。第二行包含长度为 $N$ 的字符串 $S$，仅由大写英文字母和字符 "?" 组成。字符串的每个字符代表 LC 上对应顺序的房屋。"?" 表示该房屋目前为空，其它字符表示该房屋主人的 pizzo 类别。

接下来一行包含整数 $k$（$1 \leq k \leq 26$），表示不同的 pizzo 类别数。接下来的 $k$ 行，每行包含一对整数 $c_i$ $v_i$，其中 $c_i$ 是一个大写英文字母，$1 \leq v_i \leq 10^6$，表示 pizzo 类别 $c_i$ 的房主在 PC 每次访问该房屋时需支付的金额。

保证 $S$ 中出现的每个类别都在输入的类别列表中有定义。

Output Format

输出在 LC 完全住满时，一个月内所有收集到的 pizzo 的最大可能总价值。

4
A?A?
2
A 10
B 25

140

4
A??A
2
A 10
B 25

120

Hint

由 ChatGPT 4.1 翻译