题目描述

环形展台上有 $n$ 个位置，依次编号为 $0,1,\ldots,n-1$。有些位置已经上色，其余位置尚未上色。共有 $k$ 种可用颜色，颜色 $c$ 的单点价值为 $v_c$。你需要为每个未上色的位置选择一种可用颜色，已经上色的位置不能改变。

完成配色后，对于 $n$ 的每个正因数 $d$ 和每个整数 $0\le r<d$，分别考察位置集合

若集合内所有位置的颜色相同，设其颜色为 $c$，则该集合的得分为 $(n/d)v_c$；否则得分为 $0$。将上述所有集合的得分相加，得到总分。

已知 $n$ 是某个质数的非负整数次幂，允许 $n=1$。求可以获得的最大总分。

输入格式

第一行包含一个整数 $n$。第二行包含一个长度为 $n$ 的字符串，依次描述位置 $0$ 至 $n-1$ 的颜色：大写字母表示已有颜色，? 表示未上色。

第三行包含一个整数 $k$。接下来 $k$ 行，每行包含一个大写字母 $c$ 和一个整数 $v_c$，表示一种可用颜色及其单点价值。这 $k$ 个字母互不相同。

输出格式

输出一行一个整数，表示完成配色后可以获得的最大总分。

样例输入 1

4
A?A?
2
A 3
B 8

样例输出 1

44

样例 1 解释

一种最优配色为 ABAB。$d=4$ 时，四个单点集合共得 $22$ 分；$d=2$ 时，两个集合共得 $22$ 分；$d=1$ 时，整个环不同色，得 $0$ 分。总分为 $44$。

样例输入 2

1
?
2
A 7
B 4

样例输出 2

7

样例 2 解释

只有一个位置，也只有一个计分集合。将它涂成 A，可获得 $7$ 分。

数据范围与子任务

对于所有测试数据，保证$1\le n\le10^5$，$n$ 为质数的非负整数次幂；$1\le k\le26$，$1\le v_c\le10^6$。初始出现的每种颜色都在可用颜色表中。

每个子任务内的正式测试全部通过，才获得该子任务的分数。