#include <bits/stdc++.h>
using namespace std;
const int N = 1005, ALPHA = 14;
int to[N][ALPHA], nxt[N][ALPHA];
int dph[N], sl[N], par[N], pl[N];
vector<int> tr[N];
int tot = 1;
int add_string(string &s) {
  int u = 1;
  for (int i = 0; i < s.size(); i++) {
    int c = s[i] - 'a';
    if (!to[u][c])
      to[u][c] = ++tot, par[tot] = u, dph[tot] = dph[u] + 1, pl[tot] = c;
    u = to[u][c];
  }
  return u;
}
void push_links() {
  queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (dph[u] <= 1)
      sl[u] = 1;
    else {
      int v = sl[par[u]], l = pl[u];
      while (v > 1 && !to[v][l]) v = sl[v];
      if (to[v][l]) v = to[v][l];
      sl[u] = v;
    }
    if (u != 1) tr[sl[u]].push_back(u);
    for (int i = 0; i < ALPHA; i++)
      if (to[u][i]) q.push(to[u][i]);
  }
}
int jump(int u, int c) {
  if (nxt[u][c]) return nxt[u][c];
  int v = u;
  while (v > 1 && !to[v][c]) v = sl[v];
  if (to[v][c]) v = to[v][c];
  return nxt[u][c] = v;
}
int cnt[N];
void dfs(int u, int cst) {
  cnt[u] += cst;
  for (int v : tr[u]) {
    dfs(v, cnt[u]);
  }
}
long long inf = 1e18;
long long cost[ALPHA][ALPHA][N];
int who[ALPHA][ALPHA][N];
long long DP[1 << 14][N];
int popcnt[1 << 14];
bool cmp(int x, int y) { return popcnt[x] < popcnt[y]; }
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int k;
  cin >> k;
  for (int i = 0; i < k; i++) {
    string s;
    int c;
    cin >> s >> c;
    cnt[add_string(s)] += c;
  }
  push_links();
  dfs(1, 0);
  string s;
  cin >> s;
  long long ans = 0;
  int fr = s.size();
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '?') {
      fr = i;
      break;
    }
  }
  int at = 1;
  for (int i = 0; i < fr; i++) {
    at = jump(at, s[i] - 'a');
    ans += cnt[at];
  }
  if (fr == -1) {
    cout << ans << endl;
    return 0;
  }
  vector<string> parts;
  for (int i = fr; i < s.size(); i++) {
    int l = i, r = i;
    string gap;
    for (int j = i + 1; j < s.size(); j++) {
      if (s[j] == '?') break;
      gap.push_back(s[j]);
      r = j;
    }
    parts.push_back(gap);
    i = r;
  }
  for (int i = 0; i < parts.size(); i++) {
    vector<int> done(tot + 1);
    vector<long long> memo(tot + 1);
    vector<long long> demo(tot + 1);
    string gap = parts[i];
    for (int u = 1; u <= tot; u++) {
      for (int l = 0; l < ALPHA; l++) {
        int v = jump(u, l);
        if (!done[v]) {
          long long cst = cnt[v];
          int vv = v;
          for (int j = 0; j < gap.size(); j++) {
            vv = jump(vv, gap[j] - 'a');
            cst += cnt[vv];
          }
          done[v] = true;
          memo[v] = cst;
          demo[v] = vv;
        }
        cost[i][l][u] = memo[v];
        who[i][l][u] = demo[v];
      }
    }
  }
  vector<int> masks;
  for (int i = 0; i < (1 << 14); i++) {
    popcnt[i] = __builtin_popcount(i);
    masks.push_back(i);
  }
  sort(masks.begin(), masks.end(), cmp);
  for (int i = 0; i < (1 << 14); i++) {
    for (int j = 0; j < N; j++) {
      DP[i][j] = -inf;
    }
  }
  DP[0][at] = ans;
  for (int mask : masks) {
    int i = popcnt[mask];
    if (i >= (int)parts.size()) continue;
    for (int u = 1; u <= tot; u++) {
      if (DP[mask][u] == -inf) continue;
      long long c = DP[mask][u];
      for (int k = 0; k < 14; k++) {
        if ((mask >> k) & 1) continue;
        int v = who[i][k][u];
        DP[mask | (1 << k)][v] = max(DP[mask | (1 << k)][v], c + cost[i][k][u]);
      }
    }
  }
  long long res = -inf;
  for (int mask = 0; mask < (1 << 14); mask++) {
    if (popcnt[mask] != parts.size()) continue;
    for (int u = 1; u <= tot; u++) {
      res = max(res, DP[mask][u]);
    }
  }
  cout << res << endl;
}

### Prompt

Generate a CPP solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1005, ALPHA = 14;
int to[N][ALPHA], nxt[N][ALPHA];
int dph[N], sl[N], par[N], pl[N];
vector<int> tr[N];
int tot = 1;
int add_string(string &s) {
  int u = 1;
  for (int i = 0; i < s.size(); i++) {
    int c = s[i] - 'a';
    if (!to[u][c])
      to[u][c] = ++tot, par[tot] = u, dph[tot] = dph[u] + 1, pl[tot] = c;
    u = to[u][c];
  }
  return u;
}
void push_links() {
  queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (dph[u] <= 1)
      sl[u] = 1;
    else {
      int v = sl[par[u]], l = pl[u];
      while (v > 1 && !to[v][l]) v = sl[v];
      if (to[v][l]) v = to[v][l];
      sl[u] = v;
    }
    if (u != 1) tr[sl[u]].push_back(u);
    for (int i = 0; i < ALPHA; i++)
      if (to[u][i]) q.push(to[u][i]);
  }
}
int jump(int u, int c) {
  if (nxt[u][c]) return nxt[u][c];
  int v = u;
  while (v > 1 && !to[v][c]) v = sl[v];
  if (to[v][c]) v = to[v][c];
  return nxt[u][c] = v;
}
int cnt[N];
void dfs(int u, int cst) {
  cnt[u] += cst;
  for (int v : tr[u]) {
    dfs(v, cnt[u]);
  }
}
long long inf = 1e18;
long long cost[ALPHA][ALPHA][N];
int who[ALPHA][ALPHA][N];
long long DP[1 << 14][N];
int popcnt[1 << 14];
bool cmp(int x, int y) { return popcnt[x] < popcnt[y]; }
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int k;
  cin >> k;
  for (int i = 0; i < k; i++) {
    string s;
    int c;
    cin >> s >> c;
    cnt[add_string(s)] += c;
  }
  push_links();
  dfs(1, 0);
  string s;
  cin >> s;
  long long ans = 0;
  int fr = s.size();
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '?') {
      fr = i;
      break;
    }
  }
  int at = 1;
  for (int i = 0; i < fr; i++) {
    at = jump(at, s[i] - 'a');
    ans += cnt[at];
  }
  if (fr == -1) {
    cout << ans << endl;
    return 0;
  }
  vector<string> parts;
  for (int i = fr; i < s.size(); i++) {
    int l = i, r = i;
    string gap;
    for (int j = i + 1; j < s.size(); j++) {
      if (s[j] == '?') break;
      gap.push_back(s[j]);
      r = j;
    }
    parts.push_back(gap);
    i = r;
  }
  for (int i = 0; i < parts.size(); i++) {
    vector<int> done(tot + 1);
    vector<long long> memo(tot + 1);
    vector<long long> demo(tot + 1);
    string gap = parts[i];
    for (int u = 1; u <= tot; u++) {
      for (int l = 0; l < ALPHA; l++) {
        int v = jump(u, l);
        if (!done[v]) {
          long long cst = cnt[v];
          int vv = v;
          for (int j = 0; j < gap.size(); j++) {
            vv = jump(vv, gap[j] - 'a');
            cst += cnt[vv];
          }
          done[v] = true;
          memo[v] = cst;
          demo[v] = vv;
        }
        cost[i][l][u] = memo[v];
        who[i][l][u] = demo[v];
      }
    }
  }
  vector<int> masks;
  for (int i = 0; i < (1 << 14); i++) {
    popcnt[i] = __builtin_popcount(i);
    masks.push_back(i);
  }
  sort(masks.begin(), masks.end(), cmp);
  for (int i = 0; i < (1 << 14); i++) {
    for (int j = 0; j < N; j++) {
      DP[i][j] = -inf;
    }
  }
  DP[0][at] = ans;
  for (int mask : masks) {
    int i = popcnt[mask];
    if (i >= (int)parts.size()) continue;
    for (int u = 1; u <= tot; u++) {
      if (DP[mask][u] == -inf) continue;
      long long c = DP[mask][u];
      for (int k = 0; k < 14; k++) {
        if ((mask >> k) & 1) continue;
        int v = who[i][k][u];
        DP[mask | (1 << k)][v] = max(DP[mask | (1 << k)][v], c + cost[i][k][u]);
      }
    }
  }
  long long res = -inf;
  for (int mask = 0; mask < (1 << 14); mask++) {
    if (popcnt[mask] != parts.size()) continue;
    for (int u = 1; u <= tot; u++) {
      res = max(res, DP[mask][u]);
    }
  }
  cout << res << endl;
}

```