You are given a string S and an array of strings [t_1, t_2, ..., 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 ∑_{i = 1}^{k} F(T, t_i) ⋅ c_i, where F(T, t_i) is the number of occurences of string t_i in T as a substring. For example, F(aaabaaa, 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 ≤ k ≤ 1000) — the number of strings in the array [t_1, t_2, ..., 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 ≤ |t_i| ≤ 1000, -10^6 ≤ c_i ≤ 10^6). The sum of lengths of all strings t_i does not exceed 1000.

The last line contains one string S (1 ≤ |S| ≤ 4 ⋅ 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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010, mod = 1e9 + 7, alpha = 14;
const long long inf = 1e18;
int nxt[maxn][alpha], f[maxn], to[maxn], val[maxn], C;
long long dp[1 << alpha][maxn], scr[maxn], cp[maxn];
vector<int> masks[alpha];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    int x;
    cin >> s >> x;
    int tmp = 0;
    for (char c : s) {
      if (nxt[tmp][c - 'a'] == 0) nxt[tmp][c - 'a'] = ++C;
      tmp = nxt[tmp][c - 'a'];
    }
    val[tmp] += x;
  }
  queue<int> q;
  for (int i = 0; i < 14; i++)
    if (nxt[0][i] != 0) q.push(nxt[0][i]);
  while (int((q).size())) {
    int u = q.front();
    val[u] += val[f[u]];
    q.pop();
    for (int i = 0; i < alpha; i++) {
      if (nxt[u][i] == 0)
        nxt[u][i] = nxt[f[u]][i];
      else
        f[nxt[u][i]] = nxt[f[u]][i], q.push(nxt[u][i]);
    }
  }
  for (int i = 0; i < (1 << alpha); i++) {
    masks[__builtin_popcount(i)].push_back(i);
  }
  string s;
  cin >> s;
  for (int i = 0; i < (1 << alpha); i++)
    for (int j = 0; j < maxn; j++) dp[i][j] = -inf;
  dp[0][0] = 0;
  int cnt = 0, pt = 0;
  while (true) {
    iota(to, to + C + 1, 0);
    fill(scr, scr + C + 1, 0);
    while (pt < int((s).size()) && s[pt] != '?') {
      for (int i = 0; i <= C; i++)
        to[i] = nxt[to[i]][s[pt] - 'a'], scr[i] += val[to[i]];
      pt++;
    }
    for (int msk : masks[cnt]) {
      fill(cp, cp + C + 1, -inf);
      for (int i = 0; i <= C; i++)
        cp[to[i]] = max(cp[to[i]], dp[msk][i] + scr[i]);
      for (int i = 0; i <= C; i++) dp[msk][i] = cp[i];
    }
    if (pt == int((s).size())) break;
    for (int msk : masks[cnt]) {
      for (int i = 0; i <= C; i++) {
        for (int j = 0; j < alpha; j++)
          if ((((msk) >> (j)) & 1) == 0)
            dp[msk ^ (1 << j)][nxt[i][j]] =
                max(dp[msk ^ (1 << j)][nxt[i][j]], dp[msk][i] + val[nxt[i][j]]);
      }
    }
    pt++;
    cnt++;
  }
  long long ans = -inf;
  for (int msk : masks[cnt]) {
    for (int i = 0; i <= C; i++) {
      ans = max(ans, dp[msk][i]);
    }
  }
  return cout << ans << endl, 0;
}
