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