Letters and Question Marks

题意翻译

## 题目描述 你有一个字符串 $S$ 和一个字符串数组 $[t_1, t_2, \ldots, t_k]$。每个字符串 $t_i$ 仅包含 `a` 到 `n` 以内的小写字母；$S$ 中仅包含 `a` 到 `n` 以内的小写字母和不超过 $14$ 个问号。 每一个字符串 $t_i$ 有一个整数花费 $c_i$。一个字符串 $T$ 的价值计算公式为 $\displaystyle \sum_{i = 1} ^ k F(T, t_i) \cdot c_i$，其中 $F(T, t_i)$ 表示字符串 $t_i$ 在 $T$ 中的出现次数。举例来说，$F(\texttt{aaabaaa}, \texttt{aa}) = 4$。 你需要用 `a` 到 `n` 以内的小写字母来替换 $S$ 中的问号，每个小写字母只能替换一个位置。请求出所能得到的 $S$ 的最大价值。 ## 输入格式 第一行输入一个正整数 $k ~ (1 \le k \le 1000)$，表示字符串数组 $[t_1, t_2, \ldots, t_k]$ 的大小。 接下来的 $k$ 行，每行输入一个字符串 $t_i$（仅包含 `a` 到 `n` 以内的小写字母）和一个整数 $c_i$ $(1 \le \lvert t_i \rvert \le 1000; -10 ^ 6 \le c_i \le 10 ^ 6)$。所有 $t_i$ 的长度之和不超过 $1000$。 最后一行输入一个仅包含 `a` 到 `n` 以内的小写字母和问号字符串 $S ~ (1 \le \lvert S \rvert \le 4 \cdot 10 ^ 5)$。$S$ 中的问号数量不超过 $14$。 ## 输出格式 输出一行一个整数，表示使用 `a` 到 `n` 的小写字母中不同的字母替换 $S$ 中的问号后，所能得到的最大价值。

题目描述

You are given a string $ S $ and an array of strings $ [t_1, t_2, \dots, t_k] $ . Each string $ t_i $ consists of lowercase Latin letters from a to n; $ S $ consists of lowercase Latin letters from a to n and no more than $ 14 $ question marks. Each string $ t_i $ has its cost $ c_i $ — an integer number. The value of some string $ T $ is calculated as $ \sum\limits_{i = 1}^{k} F(T, t_i) \cdot c_i $ , where $ F(T, t_i) $ is the number of occurences of string $ t_i $ in $ T $ as a substring. For example, $ F(\text{aaabaaa}, \text{aa}) = 4 $ . You have to replace all question marks in $ S $ with pairwise distinct lowercase Latin letters from a to n so the value of $ S $ is maximum possible.

输入输出格式

输入格式

The first line contains one integer $ k $ ( $ 1 \le k \le 1000 $ ) — the number of strings in the array $ [t_1, t_2, \dots, t_k] $ . Then $ k $ lines follow, each containing one string $ t_i $ (consisting of lowercase Latin letters from a to n) and one integer $ c_i $ ( $ 1 \le |t_i| \le 1000 $ , $ -10^6 \le c_i \le 10^6 $ ). The sum of lengths of all strings $ t_i $ does not exceed $ 1000 $ . The last line contains one string $ S $ ( $ 1 \le |S| \le 4 \cdot 10^5 $ ) consisting of lowercase Latin letters from a to n and question marks. The number of question marks in $ S $ is not greater than $ 14 $ .

输出格式

Print one integer — the maximum value of $ S $ after replacing all question marks with pairwise distinct lowercase Latin letters from a to n.

输入输出样例

输入样例 #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