G. Letters and Question Marks
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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

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

Examples
Input
4
abc -10
a 1
b 1
c 3
?b?
Output
5
Input
2
a 1
a 1
?
Output
2
Input
3
a 1
b 3
ab 4
ab
Output
8
Input
1
a -1
?????????????
Output
0
Input
1
a -1
??????????????
Output
-1