Вам даны строка \(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\).
Выведите одно целое число — максимальную стоимость \(S\) после замены всех знаков вопроса на попарно различные строчные латинские буквы от a до n.
4 abc -10 a 1 b 1 c 3 ?b?
5
2 a 1 a 1 ?
2
3 a 1 b 3 ab 4 ab
8
1 a -1 ?????????????
0
1 a -1 ??????????????
-1
4000 ms 1024 Mb Правила оформления программ и список ошибок при автоматической проверке задач