Letters and Question Marks
Contest: Educational Codeforces Round 84 (Rated for Div. 2)
Difficulty rating: 2800
Tags: bitmasks, dp, string suffix structures

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.

Input format:
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$$$.

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

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Example input:
4
abc -10
a 1
b 1
c 3
?b?

Example output:
5

Example input:
2
a 1
a 1
?

Example output:
2

Editorial:
Suppose we want to calculate the value of some already fixed string (we should be able to do so at least to solve the test cases without question marks). How can we do it? We can use some substring searching algorithms to calculate $$$F(S, t_i)$$$, but a better solution is to build an Aho-Corasick automaton over the array $$$[t_1, t_k]$$$, and then for each node calculate the sum of costs of all strings ending in that node (these are the strings represented by that node and the strings represented by other nodes reachable by suffix links). After that, process $$$S$$$ by the automaton and calculate the sum of the aforementioned values over all states that were reached. Building an Aho-Corasick automaton can be done in $$$O(\sum \limits_{i = 1}^{k} |t_i|)$$$, and processing the string $$$S$$$ — in $$$O(|S|)$$$.
Okay, what if we've got some question marks in our string? The first solution that comes to mind is to calculate $$$dp[i][mask][c]$$$ — we processed $$$i$$$ first positions in $$$S$$$, used a $$$mask$$$ of characters for question marks, and the current state of the automaton is $$$c$$$; then $$$dp[i][mask][c]$$$ denotes the maximum value of first $$$i$$$ characters of $$$S$$$ we could have got. But it's $$$O(L|S|2^KK)$$$, where $$$L = \sum \limits_{i = 1}^{k} |t_i|$$$ and $$$K$$$ is the size of the alphabet, which is too slow.
To speed it up, we can see that there are only $$$14$$$ positions in our string where we actually choose something in our dynamic programming. All substrings not containing question marks can be skipped in $$$O(1)$$$ as follows: for each substring of $$$S$$$ bounded by two question marks (or bounded by one question mark and one of the ends of $$$S$$$) and each state of the automaton $$$x$$$, we may precalculate the resulting state of the automaton and the change to the value of the string, if we process this substring by the automaton with the initial state $$$x$$$. This precalculation is done in $$$O(L|S|)$$$ overall, and using this, we may skip the states of dynamic programming such that $$$i$$$ is not a position with a question mark, so our complexity becomes $$$O(L2^KK + L|S|)$$$.
A note about the model solution: it's a bit more complicated because we wanted to increase the constraints to $$$|S| \le 8 \cdot 10^6$$$, but then we decided that it would be too complicated to code, so the main function still contains some parts of the code that were used to improve its complexity. We will post a clearer version of the model solution soon.