#include <bits/stdc++.h>
using namespace std;
int K;
vector<string> T;
vector<int> C;
string S;
int N;
signed long long dp[1 << 14][1010];
signed long long dp2[1 << 14][1010];
vector<int> cand[15];
const int NUMC = 14;
class Trie {
 public:
  vector<vector<int> > V;
  int find(string s) {
    int cur = 0;
    for (__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
      if ((cur = V[cur][*it + 1]) == 0) return -1;
    return cur;
  }
  void create(vector<string> S) {
    V.clear();
    V.push_back(vector<int>(NUMC + 1));
    sort(S.begin(), S.end());
    for (__typeof(S.begin()) it = S.begin(); it != S.end(); it++) {
      int cur = 0;
      for (__typeof((*it).begin()) c = (*it).begin(); c != (*it).end(); c++) {
        if (V[cur][*c + 1] == 0)
          V.push_back(vector<int>(NUMC + 1)), V[cur][*c + 1] = V.size() - 1;
        cur = V[cur][*c + 1];
      }
    }
  }
};
class ACmatch_num {
 public:
  Trie t;
  vector<int> acc;
  int ma;
  void create(vector<string> S, vector<int> C) {
    int i;
    ma = S.size();
    t.create(S);
    acc.clear();
    acc.resize(t.V.size());
    for (i = 0; i < (S.size()); i++) acc[t.find(S[i])] += C[i];
    queue<int> Q;
    for (i = 0; i < (NUMC); i++)
      if (t.V[0][i + 1]) t.V[t.V[0][i + 1]][0] = 0, Q.push(t.V[0][i + 1]);
    while (!Q.empty()) {
      int k = Q.front();
      Q.pop();
      for (i = 0; i < (NUMC); i++)
        if (t.V[k][i + 1]) {
          Q.push(t.V[k][i + 1]);
          int pre = t.V[k][0];
          while (pre && t.V[pre][i + 1] == 0) pre = t.V[pre][0];
          t.V[t.V[k][i + 1]][0] = t.V[pre][i + 1];
          acc[t.V[k][i + 1]] += acc[t.V[pre][i + 1]];
        }
    }
  }
};
ACmatch_num ac;
const int CH = 14;
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> K;
  for (i = 0; i < (K); i++) {
    cin >> s >> x;
    for (auto& c : s) c -= 'a';
    T.push_back(s);
    C.push_back(x);
  }
  ac.create(T, C);
  cin >> S;
  N = S.size();
  for (i = 0; i < (1 << CH); i++) cand[__builtin_popcount(i)].push_back(i);
  int table[1010];
  signed long long add[1010];
  for (i = 0; i < (1 << CH); i++)
    for (j = 0; j < (1005); j++) dp[i][j] = -1LL << 60;
  dp[0][0] = 0;
  int did = 0;
  int cur = 0;
  while (cur < N) {
    int tar = cur;
    while (tar < N && S[tar] != '?') tar++;
    if (cur != tar) {
      for (i = 0; i < (ac.t.V.size()); i++) {
        int cn = i;
        signed long long sc = 0;
        for (x = cur; x < tar; x++) {
          int p = cn;
          while (cn && ac.t.V[cn][S[x] - 'a' + 1] == 0) cn = ac.t.V[cn][0];
          cn = ac.t.V[cn][S[x] - 'a' + 1];
          ac.t.V[p][S[x] - 'a' + 1] = cn;
          sc += ac.acc[cn];
        }
        table[i] = cn;
        add[i] = sc;
      }
      for (auto& d : cand[did]) {
        for (i = 0; i < (ac.t.V.size()); i++)
          dp2[d][i] = dp[d][i], dp[d][i] = -1LL << 60;
      }
      for (auto& d : cand[did]) {
        for (i = 0; i < (ac.t.V.size()); i++) {
          x = table[i];
          dp[d][x] = max(dp[d][x], dp2[d][i] + add[i]);
        }
      }
    }
    cur = tar;
    if (cur == N) break;
    for (auto& d : cand[did]) {
      for (i = 0; i < (ac.t.V.size()); i++) {
        for (j = 0; j < (CH); j++)
          if ((d & (1 << j)) == 0) {
            x = y = i;
            while (x && ac.t.V[x][j + 1] == 0) x = ac.t.V[x][0];
            x = ac.t.V[x][j + 1];
            ac.t.V[y][j + 1] = x;
            dp[d | (1 << j)][x] =
                max(dp[d | (1 << j)][x], dp[d][i] + ac.acc[x]);
          }
      }
    }
    cur++;
    did++;
  }
  signed long long ret = -1LL << 60;
  for (j = 0; j < (1 << CH); j++)
    if (__builtin_popcount(j) == did) {
      for (i = 0; i < (ac.t.V.size()); i++) ret = max(ret, dp[j][i]);
    }
  cout << ret << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  return 0;
}

### 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;
int K;
vector<string> T;
vector<int> C;
string S;
int N;
signed long long dp[1 << 14][1010];
signed long long dp2[1 << 14][1010];
vector<int> cand[15];
const int NUMC = 14;
class Trie {
 public:
  vector<vector<int> > V;
  int find(string s) {
    int cur = 0;
    for (__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
      if ((cur = V[cur][*it + 1]) == 0) return -1;
    return cur;
  }
  void create(vector<string> S) {
    V.clear();
    V.push_back(vector<int>(NUMC + 1));
    sort(S.begin(), S.end());
    for (__typeof(S.begin()) it = S.begin(); it != S.end(); it++) {
      int cur = 0;
      for (__typeof((*it).begin()) c = (*it).begin(); c != (*it).end(); c++) {
        if (V[cur][*c + 1] == 0)
          V.push_back(vector<int>(NUMC + 1)), V[cur][*c + 1] = V.size() - 1;
        cur = V[cur][*c + 1];
      }
    }
  }
};
class ACmatch_num {
 public:
  Trie t;
  vector<int> acc;
  int ma;
  void create(vector<string> S, vector<int> C) {
    int i;
    ma = S.size();
    t.create(S);
    acc.clear();
    acc.resize(t.V.size());
    for (i = 0; i < (S.size()); i++) acc[t.find(S[i])] += C[i];
    queue<int> Q;
    for (i = 0; i < (NUMC); i++)
      if (t.V[0][i + 1]) t.V[t.V[0][i + 1]][0] = 0, Q.push(t.V[0][i + 1]);
    while (!Q.empty()) {
      int k = Q.front();
      Q.pop();
      for (i = 0; i < (NUMC); i++)
        if (t.V[k][i + 1]) {
          Q.push(t.V[k][i + 1]);
          int pre = t.V[k][0];
          while (pre && t.V[pre][i + 1] == 0) pre = t.V[pre][0];
          t.V[t.V[k][i + 1]][0] = t.V[pre][i + 1];
          acc[t.V[k][i + 1]] += acc[t.V[pre][i + 1]];
        }
    }
  }
};
ACmatch_num ac;
const int CH = 14;
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> K;
  for (i = 0; i < (K); i++) {
    cin >> s >> x;
    for (auto& c : s) c -= 'a';
    T.push_back(s);
    C.push_back(x);
  }
  ac.create(T, C);
  cin >> S;
  N = S.size();
  for (i = 0; i < (1 << CH); i++) cand[__builtin_popcount(i)].push_back(i);
  int table[1010];
  signed long long add[1010];
  for (i = 0; i < (1 << CH); i++)
    for (j = 0; j < (1005); j++) dp[i][j] = -1LL << 60;
  dp[0][0] = 0;
  int did = 0;
  int cur = 0;
  while (cur < N) {
    int tar = cur;
    while (tar < N && S[tar] != '?') tar++;
    if (cur != tar) {
      for (i = 0; i < (ac.t.V.size()); i++) {
        int cn = i;
        signed long long sc = 0;
        for (x = cur; x < tar; x++) {
          int p = cn;
          while (cn && ac.t.V[cn][S[x] - 'a' + 1] == 0) cn = ac.t.V[cn][0];
          cn = ac.t.V[cn][S[x] - 'a' + 1];
          ac.t.V[p][S[x] - 'a' + 1] = cn;
          sc += ac.acc[cn];
        }
        table[i] = cn;
        add[i] = sc;
      }
      for (auto& d : cand[did]) {
        for (i = 0; i < (ac.t.V.size()); i++)
          dp2[d][i] = dp[d][i], dp[d][i] = -1LL << 60;
      }
      for (auto& d : cand[did]) {
        for (i = 0; i < (ac.t.V.size()); i++) {
          x = table[i];
          dp[d][x] = max(dp[d][x], dp2[d][i] + add[i]);
        }
      }
    }
    cur = tar;
    if (cur == N) break;
    for (auto& d : cand[did]) {
      for (i = 0; i < (ac.t.V.size()); i++) {
        for (j = 0; j < (CH); j++)
          if ((d & (1 << j)) == 0) {
            x = y = i;
            while (x && ac.t.V[x][j + 1] == 0) x = ac.t.V[x][0];
            x = ac.t.V[x][j + 1];
            ac.t.V[y][j + 1] = x;
            dp[d | (1 << j)][x] =
                max(dp[d | (1 << j)][x], dp[d][i] + ac.acc[x]);
          }
      }
    }
    cur++;
    did++;
  }
  signed long long ret = -1LL << 60;
  for (j = 0; j < (1 << CH); j++)
    if (__builtin_popcount(j) == did) {
      for (i = 0; i < (ac.t.V.size()); i++) ret = max(ret, dp[j][i]);
    }
  cout << ret << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  return 0;
}

```