CF1327G.Letters and Question Marks

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.

给你一个字符串 $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$ 的值尽可能大。

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$.

第一行包含一个整数 $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$。

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

输出一个整数——将所有问号替换为互不相同的、从 a 到 n 的小写拉丁字母后，$S$ 的最大可能值。