CF1327G 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$ 中的问号后，所能得到的最大价值。