#include <bits/stdc++.h>
using namespace std;
const int K = 14;
const int N = 1000;
const long long inf = 1LL << 45;
vector<string> strs;
long long costs[N];
struct Trie {
  int arr[K];
  int link;
  long long ends;
  int p;
  char pch;
  int go[K];
  Trie(int par, char ch) {
    fill(begin(arr), end(arr), -1);
    fill(begin(go), end(go), -1);
    link = -1;
    ends = 0;
    pch = ch;
    p = par;
  }
};
vector<Trie> trie;
int go(int v, char ch);
int get_link(int v) {
  if (trie[v].link == -1) {
    if (v == 0 || trie[v].p == 0)
      trie[v].link = 0;
    else
      trie[v].link = go(get_link(trie[v].p), trie[v].pch);
  }
  return trie[v].link;
}
int go(int v, char ch) {
  int c = ch - 'a';
  if (trie[v].go[c] == -1) {
    if (trie[v].arr[c] != -1)
      trie[v].go[c] = trie[v].arr[c];
    else
      trie[v].go[c] = (v == 0) ? 0 : go(get_link(v), ch);
  }
  return trie[v].go[c];
}
void compe(int curr, vector<bool>& visited) {
  if (curr == 0 || visited[curr]) {
    return;
  }
  compe(trie[curr].link, visited);
  trie[curr].ends += trie[trie[curr].link].ends;
  visited[curr] = true;
}
void algorithm() {
  trie.clear();
  trie.emplace_back(-1, '$');
  int cnt = 0;
  for (string& s : strs) {
    int curr = 0;
    for (char i : s) {
      if (trie[curr].arr[i - 'a'] == -1) {
        trie[curr].arr[i - 'a'] = trie.size();
        trie.emplace_back(curr, i);
      }
      curr = trie[curr].arr[i - 'a'];
    }
    trie[curr].ends += costs[cnt];
    cnt++;
  }
  for (int i = 0; i < trie.size(); i++) {
    get_link(i);
    for (int a = 0; a < K; a++) {
      go(i, a + 'a');
    }
  }
  vector<bool> visited(trie.size(), false);
  visited[0] = true;
  for (int i = 1; i < trie.size(); i++) {
    compe(i, visited);
  }
}
long long dp[1 << 14][1001];
long long dp2[1 << 14][1001];
vector<long long> masks[14];
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin.exceptions(cin.failbit);
  for (int mask = 1; mask < (1 << K); mask++) {
    int cn = 0;
    for (int a = 0; a < K; a++) {
      if ((1 << a) & mask) {
        cn++;
      }
    }
    masks[cn - 1].push_back(mask);
  }
  fill(&dp[0][0], &dp[0][0] + (1 << 14) * 1001, -inf);
  fill(&dp2[0][0], &dp2[0][0] + (1 << 14) * 1001, -inf);
  int k;
  cin >> k;
  strs.resize(k);
  for (int i = 0; i < k; i++) {
    cin >> strs[i] >> costs[i];
  }
  string str;
  cin >> str;
  algorithm();
  vector<int> qs;
  for (int i = 0; i < str.size(); i++) {
    if (str[i] == '?') {
      qs.push_back(i);
    }
  }
  if (qs.empty()) {
    long long cnt = 0;
    int curr = 0;
    for (char i : str) {
      curr = go(curr, i);
      cnt += trie[curr].ends;
    }
    cout << cnt << "\n";
    return 0;
  }
  long long cnt = 0;
  int curr = 0;
  for (int i = 0; i < qs[0]; i++) {
    curr = go(curr, str[i]);
    cnt += trie[curr].ends;
  }
  for (int i = 0; i < K; i++) {
    int nxt = go(curr, 'a' + i);
    dp[1 << i][nxt] = cnt + trie[nxt].ends;
  }
  long long(*p1)[1001];
  long long(*p2)[1001];
  p1 = dp;
  p2 = dp2;
  vector<int> trans(trie.size());
  vector<long long> adds(trie.size());
  for (int i = 0; i < qs.size() - 1; i++) {
    if (qs[i + 1] - qs[i] > N) {
      int curr = 0;
      long long cnt = 0;
      for (int b = qs[i] + 1; b < qs[i] + N; b++) {
        curr = go(curr, str[b]);
      }
      for (int b = qs[i] + N; b < qs[i + 1]; b++) {
        curr = go(curr, str[b]);
        cnt += trie[curr].ends;
      }
      for (int a = 0; a < trans.size(); a++) {
        trans[a] = a;
        adds[a] = 0;
        for (int b = qs[i] + 1; b < qs[i] + N; b++) {
          trans[a] = go(trans[a], str[b]);
          adds[a] += trie[trans[a]].ends;
        }
        trans[a] = curr;
        adds[a] += cnt;
      }
    } else {
      for (int a = 0; a < trans.size(); a++) {
        trans[a] = a;
        adds[a] = 0;
        for (int b = qs[i] + 1; b < qs[i + 1]; b++) {
          trans[a] = go(trans[a], str[b]);
          adds[a] += trie[trans[a]].ends;
        }
      }
    }
    for (int mask : masks[i]) {
      for (int a = 0; a < trans.size(); a++) {
        for (int add = 0; add < K; add++) {
          if (!(mask & (1 << add))) {
            long long nxt = go(trans[a], 'a' + add);
            p2[mask + (1 << add)][nxt] =
                max(p2[mask + (1 << add)][nxt],
                    adds[a] + trie[nxt].ends + p1[mask][a]);
          }
        }
        p1[mask][a] = -inf;
      }
    }
    swap(p2, p1);
  }
  long long ans = -inf;
  if (str.size() - qs.back() > N + 1) {
    int curr = 0;
    long long reward = 0;
    for (int b = qs.back() + 1; b < qs.back() + N; b++) {
      curr = go(curr, str[b]);
    }
    for (int b = qs.back() + N; b < str.size(); b++) {
      curr = go(curr, str[b]);
      reward += trie[curr].ends;
    }
    for (int a = 0; a < trie.size(); a++) {
      cnt = -inf;
      for (int mask = 1; mask < (1 << K); mask++) {
        cnt = max(cnt, p1[mask][a]);
      }
      curr = a;
      for (int i = qs.back() + 1; i < qs.back() + N; i++) {
        curr = go(curr, str[i]);
        cnt += trie[curr].ends;
      }
      ans = max(ans, cnt + reward);
    }
  } else {
    for (int a = 0; a < trie.size(); a++) {
      cnt = -inf;
      for (int mask = 1; mask < (1 << K); mask++) {
        cnt = max(cnt, p1[mask][a]);
      }
      curr = a;
      for (int i = qs.back() + 1; i < str.size(); i++) {
        curr = go(curr, str[i]);
        cnt += trie[curr].ends;
      }
      ans = max(ans, cnt);
    }
  }
  cout << ans << "\n";
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 K = 14;
const int N = 1000;
const long long inf = 1LL << 45;
vector<string> strs;
long long costs[N];
struct Trie {
  int arr[K];
  int link;
  long long ends;
  int p;
  char pch;
  int go[K];
  Trie(int par, char ch) {
    fill(begin(arr), end(arr), -1);
    fill(begin(go), end(go), -1);
    link = -1;
    ends = 0;
    pch = ch;
    p = par;
  }
};
vector<Trie> trie;
int go(int v, char ch);
int get_link(int v) {
  if (trie[v].link == -1) {
    if (v == 0 || trie[v].p == 0)
      trie[v].link = 0;
    else
      trie[v].link = go(get_link(trie[v].p), trie[v].pch);
  }
  return trie[v].link;
}
int go(int v, char ch) {
  int c = ch - 'a';
  if (trie[v].go[c] == -1) {
    if (trie[v].arr[c] != -1)
      trie[v].go[c] = trie[v].arr[c];
    else
      trie[v].go[c] = (v == 0) ? 0 : go(get_link(v), ch);
  }
  return trie[v].go[c];
}
void compe(int curr, vector<bool>& visited) {
  if (curr == 0 || visited[curr]) {
    return;
  }
  compe(trie[curr].link, visited);
  trie[curr].ends += trie[trie[curr].link].ends;
  visited[curr] = true;
}
void algorithm() {
  trie.clear();
  trie.emplace_back(-1, '$');
  int cnt = 0;
  for (string& s : strs) {
    int curr = 0;
    for (char i : s) {
      if (trie[curr].arr[i - 'a'] == -1) {
        trie[curr].arr[i - 'a'] = trie.size();
        trie.emplace_back(curr, i);
      }
      curr = trie[curr].arr[i - 'a'];
    }
    trie[curr].ends += costs[cnt];
    cnt++;
  }
  for (int i = 0; i < trie.size(); i++) {
    get_link(i);
    for (int a = 0; a < K; a++) {
      go(i, a + 'a');
    }
  }
  vector<bool> visited(trie.size(), false);
  visited[0] = true;
  for (int i = 1; i < trie.size(); i++) {
    compe(i, visited);
  }
}
long long dp[1 << 14][1001];
long long dp2[1 << 14][1001];
vector<long long> masks[14];
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin.exceptions(cin.failbit);
  for (int mask = 1; mask < (1 << K); mask++) {
    int cn = 0;
    for (int a = 0; a < K; a++) {
      if ((1 << a) & mask) {
        cn++;
      }
    }
    masks[cn - 1].push_back(mask);
  }
  fill(&dp[0][0], &dp[0][0] + (1 << 14) * 1001, -inf);
  fill(&dp2[0][0], &dp2[0][0] + (1 << 14) * 1001, -inf);
  int k;
  cin >> k;
  strs.resize(k);
  for (int i = 0; i < k; i++) {
    cin >> strs[i] >> costs[i];
  }
  string str;
  cin >> str;
  algorithm();
  vector<int> qs;
  for (int i = 0; i < str.size(); i++) {
    if (str[i] == '?') {
      qs.push_back(i);
    }
  }
  if (qs.empty()) {
    long long cnt = 0;
    int curr = 0;
    for (char i : str) {
      curr = go(curr, i);
      cnt += trie[curr].ends;
    }
    cout << cnt << "\n";
    return 0;
  }
  long long cnt = 0;
  int curr = 0;
  for (int i = 0; i < qs[0]; i++) {
    curr = go(curr, str[i]);
    cnt += trie[curr].ends;
  }
  for (int i = 0; i < K; i++) {
    int nxt = go(curr, 'a' + i);
    dp[1 << i][nxt] = cnt + trie[nxt].ends;
  }
  long long(*p1)[1001];
  long long(*p2)[1001];
  p1 = dp;
  p2 = dp2;
  vector<int> trans(trie.size());
  vector<long long> adds(trie.size());
  for (int i = 0; i < qs.size() - 1; i++) {
    if (qs[i + 1] - qs[i] > N) {
      int curr = 0;
      long long cnt = 0;
      for (int b = qs[i] + 1; b < qs[i] + N; b++) {
        curr = go(curr, str[b]);
      }
      for (int b = qs[i] + N; b < qs[i + 1]; b++) {
        curr = go(curr, str[b]);
        cnt += trie[curr].ends;
      }
      for (int a = 0; a < trans.size(); a++) {
        trans[a] = a;
        adds[a] = 0;
        for (int b = qs[i] + 1; b < qs[i] + N; b++) {
          trans[a] = go(trans[a], str[b]);
          adds[a] += trie[trans[a]].ends;
        }
        trans[a] = curr;
        adds[a] += cnt;
      }
    } else {
      for (int a = 0; a < trans.size(); a++) {
        trans[a] = a;
        adds[a] = 0;
        for (int b = qs[i] + 1; b < qs[i + 1]; b++) {
          trans[a] = go(trans[a], str[b]);
          adds[a] += trie[trans[a]].ends;
        }
      }
    }
    for (int mask : masks[i]) {
      for (int a = 0; a < trans.size(); a++) {
        for (int add = 0; add < K; add++) {
          if (!(mask & (1 << add))) {
            long long nxt = go(trans[a], 'a' + add);
            p2[mask + (1 << add)][nxt] =
                max(p2[mask + (1 << add)][nxt],
                    adds[a] + trie[nxt].ends + p1[mask][a]);
          }
        }
        p1[mask][a] = -inf;
      }
    }
    swap(p2, p1);
  }
  long long ans = -inf;
  if (str.size() - qs.back() > N + 1) {
    int curr = 0;
    long long reward = 0;
    for (int b = qs.back() + 1; b < qs.back() + N; b++) {
      curr = go(curr, str[b]);
    }
    for (int b = qs.back() + N; b < str.size(); b++) {
      curr = go(curr, str[b]);
      reward += trie[curr].ends;
    }
    for (int a = 0; a < trie.size(); a++) {
      cnt = -inf;
      for (int mask = 1; mask < (1 << K); mask++) {
        cnt = max(cnt, p1[mask][a]);
      }
      curr = a;
      for (int i = qs.back() + 1; i < qs.back() + N; i++) {
        curr = go(curr, str[i]);
        cnt += trie[curr].ends;
      }
      ans = max(ans, cnt + reward);
    }
  } else {
    for (int a = 0; a < trie.size(); a++) {
      cnt = -inf;
      for (int mask = 1; mask < (1 << K); mask++) {
        cnt = max(cnt, p1[mask][a]);
      }
      curr = a;
      for (int i = qs.back() + 1; i < str.size(); i++) {
        curr = go(curr, str[i]);
        cnt += trie[curr].ends;
      }
      ans = max(ans, cnt);
    }
  }
  cout << ans << "\n";
}

```