Lavish Circle (LC) 是镇上住宅区一条时尚的环形大道。LC 上的房屋极其昂贵，其中一些目前是空的。LC 在镇黑帮的严密控制之下，他们希望用忠于黑帮的新房主来填补空置的房屋。当 LC 被完全填满时，每位房主将居住在 LC 上的一栋房屋中。LC 是一条编号从 $1$ 到 $N$ 的环形房屋大道，即对于 $i < N$，$i$ 号房屋和 $i+1$ 号房屋相邻，且 $N$ 号房屋和 $1$ 号房屋也相邻。

房主（包括现有的和新来的）根据他们每月能向黑帮支付的保护费金额分为几个类别。这笔钱被称为“保护费”（pizzo），通常由被称为“保护费收取人”（PC）的人员收取。黑帮雇佣了一群这样的人。

PC 的工作是每月绕整个 LC 恰好一圈，并从旅途中选定的房屋收取保护费。PC 旅途中所有选定的房屋必须属于相同的保护费类别。旅程必须在同一栋房屋开始和结束，这是检查 PC 是否正确完成旅程的方式。保护费仅在旅程开始或结束时从该房屋收取一次。在旅程中，PC 总是向前移动固定的房屋数量，直到再次到达起始房屋。也就是说，PC 每次移动跳过的房屋数量是一个非负整数 $d$，该数值在 PC 的整个旅程中保持不变。必须满足 $(d + 1)$ 整除 $N$。

黑帮希望尽可能多地雇佣 PC。当然，雇佣多名 PC 意味着某些房主很可能每月需要支付不止一次保护费，但黑帮并不在意……不幸的是，这里有一个复杂的情况。PC 是和平的公民，在正常情况下他们不会互相射击。然而，当两名 PC 发现他们在各自的收取旅程中访问了同一组房屋时（无论他们访问房屋的顺序如何），收取人往往会互相射击，从而引来警察，这是黑帮不惜一切代价想要避免的行为。因此，不能同时雇佣任何可能互相射击的收取人。

所有收取的保护费总价值也取决于新入住房屋的房主类别。黑帮决定每位新房主的类别。显然，黑帮希望最大化他们的收入。你已被聘为分析师，以找出当 LC 被完全且适当地填满时，一个月内所有收取的保护费的最大可能总价值。黑帮将根据你的建议决定每位新房主的保护费类别。LC 上的房屋数量 $N$ 是某个素数的非负整数次幂。

输入格式

第一行包含整数 $N$ ($1 \le N \le 10^5$)，它是某个素数 $p$ 的非负整数次幂。第二行包含长度为 $N$ 的字符串 $S$，仅由英文字母大写和字符“?”组成。字符串中的字符按顺序代表 LC 上的房屋。字符“?”代表当前空置的房屋，其他字符代表房主的保护费类别。

下一行包含整数 $k$ ($1 \le k \le 26$)，即不同保护费类别的数量。接下来的 $k$ 行，每行包含一个整数对 $c_i$ 和 $v_i$，其中 $c_i$ 是一个大写英文字母，$1 \le v_i \le 10^6$ 是保护费类别为 $c_i$ 的房主在 PC 一次访问中支付的金额。

保证对于 $S$ 中出现的每个类别，都有一个定义其支付金额的 $c_i$ 和 $v_i$ 对。

输出格式

输出当 LC 被完全填满时，一个月内所有收取的保护费的最大可能总价值。

样例

样例输入 1

4
A?A?
2
A 10
B 25

样例输出 1

140

样例输入 2

4
A??A
2
A 10
B 25

样例输出 2

120