← 返回题目列表

Codeforces · 1327/G

G. 字母和问号

中文机器翻译题面 查看原题

给定一个字符串 $$$S$$$ 和一个字符串数组 $$$[t_1, t_2, \dots, t_k]$$$。每个字符串 $$$t_i$$$ 由 a 到 n 的小写拉丁字母组成; $$$S$$$ 由 a 到 n 的小写拉丁字母和不超过 $$$14$$$ 问号组成。

每个字符串 $$$t_i$$$ 都有其成本 $$$c_i$$$ — 一个整数。某个字符串 $$$T$$$ 的值计算为 $$$\sum\limits_{i = 1}^{k} F(T, t_i) \cdot c_i$$$,其中 $$$F(T, t_i)$$$ 是字符串 $$$t_i$$$ 作为子字符串在 $$$T$$$ 中出现的次数。例如,$$$F(\text{aaabaaa}, \text{aa}) = 4$$$。

您必须将 $$$S$$$ 中的所有问号替换为从 a 到 n 的成对不同的小写拉丁字母,以便 $$$S$$$ 的值尽可能最大。

输入

第一行包含一个整数 $$$k$$$ ($$$1 \le k \le 1000$$$) — 数组 $$$[t_1, t_2, \dots, t_k]$$$ 中的字符串数量。

接下来是 $$$k$$$ 行,每行包含一个字符串 $$$t_i$$$ (由 a 到 n 的小写拉丁字母组成)和一个整数 $$$c_i$$$ ($$$1 \le |t_i| \le 1000$$$, $$$-10^6 \le c_i \le 10^6$$$)。所有字符串$$$t_i$$$的长度总和不超过$$$1000$$$。

最后一行包含一个字符串 $$$S$$$ ($$$1 \le |S| \le 4 \cdot 10^5$$$),由 a 到 n 的小写拉丁字母和问号组成。 $$$S$$$ 中的问号数量不大于 $$$14$$$。

输出

打印一个整数 — 将所有问号替换为从 a 到 n 的成对不同的小写拉丁字母后 $$$S$$$ 的最大值。

示例

输入 #1

4
abc -10
a 1
b 1
c 3
?b?

输出 #1

5

输入 #2

2
a 1
a 1
?

输出 #2

2

输入 #3

3
a 1
b 3
ab 4
ab

输出 #3

8

输入#4

1
a -1
?????????????

输出#4

0

输入 #5

1
a -1
??????????????

输出 #5

-1