#3089. 「BJOI2019」奥术神杖

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: EntropyIncreaser

题目描述

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 ,表示每种咒语。

输出格式

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

样例

样例输入 1

4 3
....
1 2
2 2
3 1

样例输出 1

2019

样例解释 1

法杖最终神力值为 2

样例输入 2

5 4
..0..
0 2
00 2
01 4
10 3

样例输出 2

11012

样例解释 2

法杖最终神力值为 \sqrt[3]{2 \times 3 \times 4}

样例输入 3

18 6
...2.1.0.1..1.0..1
011 6
111 4
010 12
121 7
101 5
10 3

样例输出 3

121211203112120121

数据范围与提示

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

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

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