#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int pwr(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (ans * 1LL * a) % mod;
    a = (a * 1LL * a) % mod;
    b >>= 1;
  }
  return ans;
}
const int K = 1005;
string s[K];
int cost[K];
const int CHAR = 14;
class AhoCora {
 public:
  struct Node {
    int ch[CHAR];
    int link;
    long long val;
    int id;
    int go[CHAR];
  };
  vector<Node> nd;
  vector<int> Q;
  int qs, qe;
  int size;
  int createNode() {
    int ret = size++;
    nd.emplace_back();
    Q.emplace_back();
    for (int i = 0; i < CHAR; i++) {
      nd[ret].go[i] = nd[ret].ch[i] = -1;
    }
    nd[ret].val = 0;
    return ret;
  }
  void init() {
    size = 0;
    nd.clear();
    Q.clear();
    createNode();
  }
  template <typename A>
  void add(A str, const int &sz, const int &id) {
    int cur = 0;
    for (int i = 0; i < sz; i++) {
      int c = str[i] - 'a';
      if (nd[cur].ch[c] == -1) {
        int nnd = createNode();
        nd[cur].ch[c] = nnd;
      }
      cur = nd[cur].ch[c];
    }
    nd[cur].val += cost[id];
    nd[cur].id = id;
  }
  inline int next(int u, int c) {
    if (nd[u].go[c] != -1) return nd[u].go[c];
    int uu = u;
    while (u && nd[u].ch[c] < 0) u = nd[u].link;
    return nd[uu].go[c] = (nd[u].ch[c] < 0) ? 0 : nd[u].ch[c];
  }
  void computelink() {
    qs = qe = 0;
    nd[0].link = 0;
    for (int x, i = 0; i < CHAR; i++) {
      if ((x = nd[0].ch[i]) >= 0) {
        Q[qe++] = x;
        nd[x].link = 0;
      }
    }
    while (qs < qe) {
      int u = Q[qs++];
      for (int v, i = 0; i < CHAR; i++) {
        if ((v = nd[u].ch[i]) >= 0) {
          Q[qe++] = v;
          int m = nd[u].link;
          int L = nd[v].link = next(m, i);
          nd[v].val += nd[L].val;
        }
      }
    }
  }
} acc;
pair<int, long long> skip[K][CHAR];
long long dp[1 << CHAR][K];
int main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  acc.init();
  int k;
  cin >> k;
  for (int i = 1; i <= k; i++) {
    cin >> s[i];
    cin >> cost[i];
    acc.add(s[i], s[i].size(), i);
  }
  acc.computelink();
  string p;
  cin >> p;
  vector<int> v;
  for (int i = 0; i < p.size(); i++) {
    if (p[i] == '?') {
      v.push_back(i);
    }
  }
  int st = 0;
  for (int i = 0; i < acc.nd.size(); i++) {
    for (int j = 0; j < v.size(); j++) {
      int pt = i;
      long long x = 0;
      int jj = v[j];
      for (int k = jj + 1; k < p.size() && p[k] != '?'; k++) {
        pt = acc.next(pt, p[k] - 'a');
        x += acc.nd[pt].val;
      }
      skip[i][j] = {pt, x};
    }
  }
  int node = 0;
  for (int i = 0; i < K; i++) {
    for (int j = 0; j < (1 << CHAR); j++) {
      dp[j][i] = -1e18;
    }
  }
  long long now = 0;
  while (st < p.size() && p[st] != '?') {
    node = acc.next(node, p[st] - 'a');
    st++;
    now += acc.nd[node].val;
  }
  dp[0][node] = now;
  for (int mask = 0; mask < (1 << CHAR); mask++) {
    for (int i = 0; i < acc.nd.size(); i++) {
      if (dp[mask][i] == -1e18) continue;
      for (int j = 0; j < CHAR; j++) {
        if ((mask >> j) & 1) continue;
        long long newval = dp[mask][i];
        int mm = __builtin_popcount(mask);
        int in = acc.next(i, j);
        newval += acc.nd[in].val;
        newval += skip[in][mm].second;
        in = skip[in][mm].first;
        dp[mask ^ (1 << j)][in] = max(dp[mask ^ (1 << j)][in], newval);
      }
    }
  }
  long long ans = -1e18;
  for (int mask = 0; mask < (1 << CHAR); mask++) {
    for (int j = 0; j < acc.nd.size(); j++) {
      if (__builtin_popcount(mask) == v.size()) {
        ans = max(ans, dp[mask][j]);
      }
    }
  }
  cout << ans;
  return 0;
}

### Prompt

Please create a solution in cpp 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 mod = 998244353;
int pwr(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (ans * 1LL * a) % mod;
    a = (a * 1LL * a) % mod;
    b >>= 1;
  }
  return ans;
}
const int K = 1005;
string s[K];
int cost[K];
const int CHAR = 14;
class AhoCora {
 public:
  struct Node {
    int ch[CHAR];
    int link;
    long long val;
    int id;
    int go[CHAR];
  };
  vector<Node> nd;
  vector<int> Q;
  int qs, qe;
  int size;
  int createNode() {
    int ret = size++;
    nd.emplace_back();
    Q.emplace_back();
    for (int i = 0; i < CHAR; i++) {
      nd[ret].go[i] = nd[ret].ch[i] = -1;
    }
    nd[ret].val = 0;
    return ret;
  }
  void init() {
    size = 0;
    nd.clear();
    Q.clear();
    createNode();
  }
  template <typename A>
  void add(A str, const int &sz, const int &id) {
    int cur = 0;
    for (int i = 0; i < sz; i++) {
      int c = str[i] - 'a';
      if (nd[cur].ch[c] == -1) {
        int nnd = createNode();
        nd[cur].ch[c] = nnd;
      }
      cur = nd[cur].ch[c];
    }
    nd[cur].val += cost[id];
    nd[cur].id = id;
  }
  inline int next(int u, int c) {
    if (nd[u].go[c] != -1) return nd[u].go[c];
    int uu = u;
    while (u && nd[u].ch[c] < 0) u = nd[u].link;
    return nd[uu].go[c] = (nd[u].ch[c] < 0) ? 0 : nd[u].ch[c];
  }
  void computelink() {
    qs = qe = 0;
    nd[0].link = 0;
    for (int x, i = 0; i < CHAR; i++) {
      if ((x = nd[0].ch[i]) >= 0) {
        Q[qe++] = x;
        nd[x].link = 0;
      }
    }
    while (qs < qe) {
      int u = Q[qs++];
      for (int v, i = 0; i < CHAR; i++) {
        if ((v = nd[u].ch[i]) >= 0) {
          Q[qe++] = v;
          int m = nd[u].link;
          int L = nd[v].link = next(m, i);
          nd[v].val += nd[L].val;
        }
      }
    }
  }
} acc;
pair<int, long long> skip[K][CHAR];
long long dp[1 << CHAR][K];
int main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  acc.init();
  int k;
  cin >> k;
  for (int i = 1; i <= k; i++) {
    cin >> s[i];
    cin >> cost[i];
    acc.add(s[i], s[i].size(), i);
  }
  acc.computelink();
  string p;
  cin >> p;
  vector<int> v;
  for (int i = 0; i < p.size(); i++) {
    if (p[i] == '?') {
      v.push_back(i);
    }
  }
  int st = 0;
  for (int i = 0; i < acc.nd.size(); i++) {
    for (int j = 0; j < v.size(); j++) {
      int pt = i;
      long long x = 0;
      int jj = v[j];
      for (int k = jj + 1; k < p.size() && p[k] != '?'; k++) {
        pt = acc.next(pt, p[k] - 'a');
        x += acc.nd[pt].val;
      }
      skip[i][j] = {pt, x};
    }
  }
  int node = 0;
  for (int i = 0; i < K; i++) {
    for (int j = 0; j < (1 << CHAR); j++) {
      dp[j][i] = -1e18;
    }
  }
  long long now = 0;
  while (st < p.size() && p[st] != '?') {
    node = acc.next(node, p[st] - 'a');
    st++;
    now += acc.nd[node].val;
  }
  dp[0][node] = now;
  for (int mask = 0; mask < (1 << CHAR); mask++) {
    for (int i = 0; i < acc.nd.size(); i++) {
      if (dp[mask][i] == -1e18) continue;
      for (int j = 0; j < CHAR; j++) {
        if ((mask >> j) & 1) continue;
        long long newval = dp[mask][i];
        int mm = __builtin_popcount(mask);
        int in = acc.next(i, j);
        newval += acc.nd[in].val;
        newval += skip[in][mm].second;
        in = skip[in][mm].first;
        dp[mask ^ (1 << j)][in] = max(dp[mask ^ (1 << j)][in], newval);
      }
    }
  }
  long long ans = -1e18;
  for (int mask = 0; mask < (1 << CHAR); mask++) {
    for (int j = 0; j < acc.nd.size(); j++) {
      if (__builtin_popcount(mask) == v.size()) {
        ans = max(ans, dp[mask][j]);
      }
    }
  }
  cout << ans;
  return 0;
}

```