A5851. 「BJOI2019」奥术神杖

Bezorath 大陆抵抗地灾军团入侵的战争进入了僵持的阶段，世世代代生活在 Bezorath 这片大陆的精灵们开始寻找远古时代诸神遗留的神器，试图借助神器的神秘力量帮助她们战胜地灾军团。

在付出了惨痛的代价后，精灵们从步步凶险的远古战场取回了一件保存尚完好的神杖。但在经历过那场所有史书都视为禁忌的“诸神黄昏之战”后，神杖上镶嵌的奥术宝石已经残缺，神力也几乎消耗殆尽。精灵高层在至高会议中决定以举国之力收集残存至今的奥术宝石，并重金悬赏天下能工巧匠修复这件神杖。

你作为神术一脉第五百零一位传人，接受了这个艰巨而神圣的使命。 神杖上从左到右镶嵌了 $n$ 颗奥术宝石，奥术宝石一共有 $10$ 种，用数字 0123456789 表示。有些位置的宝石已经残缺，用 . 表示，你需要用完好的奥术宝石填补每一处残缺的部分（每种奥术宝石个数不限，且不能够更换未残缺的宝石）。古老的魔法书上记载了 $m$ 种咒语 $(S_i,V_i)$，其中 $S_i$ 是一个非空数字串，$V_i$ 是这种组合能够激发的神力。

神杖的初始神力值 $\mathrm{Magic} = 1$，每当神杖中出现了连续一段宝石与 $S_i$ 相等时，神力值 $\mathrm{Magic}$ 就会乘以 $V_i$。但神杖如果包含了太多咒语就不再纯净导致神力降低：设 $c$ 为神杖包含的咒语个数（若咒语类别相同但出现位置不同视为多次），神杖最终的神力值为 $\sqrt[c]{\mathrm{Magic}}$。（若 $c = 0$ 则神杖最终神力值为 $1$。）

例如有两种咒语 $(01,3)$ 、$(10,4)$，那么神杖 0101 的神力值为 $\sqrt[3]{ 3 \times 4 \times 3}$。

你需要使修复好的神杖的最终的神力值最大，输出任何一个解即可。

第一行两个正整数 $n,m$，表示宝石数和咒语数。

第二行为一个长度为 $n$ 的字符串 $T$，表示初始的神杖。

接下来 $m$ 行每行一个非空数字串 $S_i$ 和一个正整数 $V_i$，表示每种咒语。

输出最终神杖上从左到右镶嵌的宝石，多解时任意输出一个即可。

设 $s = \sum_{i=1}^{m} |S_i|$，即所有咒语的串长之和。

| 测试点 | $n\le$ | $s\le$ | 特殊性质 |
|:-:|:-:|:-:|:-:|
| $1\sim 3$ | $6$ | $20$ ||
| $4\sim 5$ | $501$ | $5$ ||
| $6$ | $501$ | $501$ | 所有 $V_i$ 相同 |
| $7$ | $501$ | $501$ | $V_i$ 最多只有 $2$ 种不同的取值 |
| $8$ | $501$ | $501$ | $V_i$ 最多只有 $3$ 种不同的取值 |
| $9\sim 11$ | $501$ | $501$ | $T$ 中全部由 . 组成 |
| $12\sim 13$ | $501$ | $501$ | $T$ 最多只有 $3$ 个位置是 . |
| $14\sim 16$ | $501$ | $501$ | |
| $17\sim 20$ | $1501$ | $1501$ | |

对于 $100\%$ 的数据，满足 $1\le n, m, s \le 1501, 1\le V_i\le 10^9$。