G. Буквы и знаки вопроса
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

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