给定一个字符串 $$$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