Вам даны строка $$$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
