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.

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$.

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