#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <typename T>
T sqr(T a) {
  return a * a;
}
template <typename T>
int sign(T a) {
  if (a == 0) return 0;
  return (a > 0 ? 1 : -1);
}
template <typename T>
bool uax(T& a, const T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool uin(T& a, const T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2>& p) {
  out << p.first << ' ' << p.second;
  return out;
}
mt19937_64 rnd(0);
const int LOG = 30;
const int N = (int)2e5 + 7;
const int MAXN = (int)1e3 + 7;
const int MOD = (int)998244353;
const int INF = (int)1e9 + 7;
const int CONST = 450;
const long long LINF = (int64_t)1e17;
const long double PI = 3.1415926535897932384626433832795;
const long double EPS = 1;
struct Node {
  Node *suff, *edg[14], *shift[15];
  long long sum, cost, sum_shift[15];
  int node;
  Node() {
    sum = cost = 0;
    suff = nullptr;
    fill(edg, edg + 14, nullptr);
    fill(shift, shift + 14, nullptr);
  }
};
int node;
Node arr[MAXN];
Node* new_node() {
  arr[node].node = node;
  return &arr[node++];
}
Node *fict, *root;
void add(Node* v, const string& s, int cost) {
  for (char c : s) {
    int pos = c - 'a';
    if (!v->edg[pos]) v->edg[pos] = new_node();
    v = v->edg[pos];
  }
  v->cost += cost;
}
Node* go(Node* v, int pos) {
  if (v->edg[pos]) return v->edg[pos];
  return go(v->suff, pos);
}
pair<Node*, long long> trav(Node* v, const string& s) {
  long long sum = v->sum;
  for (char c : s) {
    int pos = c - 'a';
    v = v->edg[pos];
    sum += v->sum;
  }
  return make_pair(v, sum);
}
void calc_suff() {
  root->suff = fict;
  for (int i = 0; i < 14; i++) fict->edg[i] = root;
  queue<Node*> q;
  q.push(root);
  while (!q.empty()) {
    auto v = q.front();
    q.pop();
    for (int i = 0; i < 14; i++) {
      if (!v->edg[i]) {
        v->edg[i] = go(v, i);
        continue;
      }
      Node *to = v->edg[i], *suff = go(v->suff, i);
      to->suff = suff;
      to->sum = to->cost + suff->sum;
      q.push(v->edg[i]);
    }
  }
}
string s;
int n, bit[N];
vector<string> seq;
long long dp[1 << 14][MAXN];
void solve() {
  for (int i = 1; i < N; i++) bit[i] = bit[i / 2] + (i & 1);
  fict = new_node(), root = new_node();
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    int cost;
    cin >> cost;
    add(root, s, cost);
  }
  cin >> s;
  calc_suff();
  int ind = 0, sz = (int)s.size();
  while (ind < sz) {
    string cur = "";
    while (ind < sz && s[ind] != '?') cur += s[ind++];
    seq.push_back(cur);
    ind++;
  }
  if (s.back() == '?') seq.push_back("");
  int seg = (int)seq.size();
  for (int i = 0; i < node; i++) {
    for (int j = 0; j < seg; j++)
      tie(arr[i].shift[j], arr[i].sum_shift[j]) = trav(&arr[i], seq[j]);
  }
  for (int i = 0; i < (1 << 14); i++) fill(dp[i], dp[i] + node, -LINF);
  auto st = trav(root, seq[0]);
  dp[0][st.first->node] = st.second;
  long long ans = -LINF;
  for (int mask = 0; mask < (1 << 14); mask++) {
    if (bit[mask] == seg - 1) {
      for (int cnode = 1; cnode < node; cnode++) uax(ans, dp[mask][cnode]);
    }
    if (bit[mask] >= seg - 1) continue;
    for (int cnode = 1; cnode < node; cnode++) {
      if (dp[mask][cnode] == -LINF) continue;
      for (int let = 0; let < 14; let++) {
        if (mask & (1 << let)) continue;
        int nmask = mask | (1 << let);
        int nnode = arr[cnode].edg[let]->node;
        long long add = arr[nnode].sum_shift[bit[nmask]];
        nnode = arr[nnode].shift[bit[nmask]]->node;
        uax(dp[nmask][nnode], dp[mask][cnode] + add);
      }
    }
  }
  cout << ans;
}
int main() {
  double start = clock();
  cout << fixed << setprecision(20);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  rnd.seed(time(0));
  int t = 1;
  for (int i = 0; i < t; i++) {
    solve();
  }
}

### 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>
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <typename T>
T sqr(T a) {
  return a * a;
}
template <typename T>
int sign(T a) {
  if (a == 0) return 0;
  return (a > 0 ? 1 : -1);
}
template <typename T>
bool uax(T& a, const T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool uin(T& a, const T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2>& p) {
  out << p.first << ' ' << p.second;
  return out;
}
mt19937_64 rnd(0);
const int LOG = 30;
const int N = (int)2e5 + 7;
const int MAXN = (int)1e3 + 7;
const int MOD = (int)998244353;
const int INF = (int)1e9 + 7;
const int CONST = 450;
const long long LINF = (int64_t)1e17;
const long double PI = 3.1415926535897932384626433832795;
const long double EPS = 1;
struct Node {
  Node *suff, *edg[14], *shift[15];
  long long sum, cost, sum_shift[15];
  int node;
  Node() {
    sum = cost = 0;
    suff = nullptr;
    fill(edg, edg + 14, nullptr);
    fill(shift, shift + 14, nullptr);
  }
};
int node;
Node arr[MAXN];
Node* new_node() {
  arr[node].node = node;
  return &arr[node++];
}
Node *fict, *root;
void add(Node* v, const string& s, int cost) {
  for (char c : s) {
    int pos = c - 'a';
    if (!v->edg[pos]) v->edg[pos] = new_node();
    v = v->edg[pos];
  }
  v->cost += cost;
}
Node* go(Node* v, int pos) {
  if (v->edg[pos]) return v->edg[pos];
  return go(v->suff, pos);
}
pair<Node*, long long> trav(Node* v, const string& s) {
  long long sum = v->sum;
  for (char c : s) {
    int pos = c - 'a';
    v = v->edg[pos];
    sum += v->sum;
  }
  return make_pair(v, sum);
}
void calc_suff() {
  root->suff = fict;
  for (int i = 0; i < 14; i++) fict->edg[i] = root;
  queue<Node*> q;
  q.push(root);
  while (!q.empty()) {
    auto v = q.front();
    q.pop();
    for (int i = 0; i < 14; i++) {
      if (!v->edg[i]) {
        v->edg[i] = go(v, i);
        continue;
      }
      Node *to = v->edg[i], *suff = go(v->suff, i);
      to->suff = suff;
      to->sum = to->cost + suff->sum;
      q.push(v->edg[i]);
    }
  }
}
string s;
int n, bit[N];
vector<string> seq;
long long dp[1 << 14][MAXN];
void solve() {
  for (int i = 1; i < N; i++) bit[i] = bit[i / 2] + (i & 1);
  fict = new_node(), root = new_node();
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    int cost;
    cin >> cost;
    add(root, s, cost);
  }
  cin >> s;
  calc_suff();
  int ind = 0, sz = (int)s.size();
  while (ind < sz) {
    string cur = "";
    while (ind < sz && s[ind] != '?') cur += s[ind++];
    seq.push_back(cur);
    ind++;
  }
  if (s.back() == '?') seq.push_back("");
  int seg = (int)seq.size();
  for (int i = 0; i < node; i++) {
    for (int j = 0; j < seg; j++)
      tie(arr[i].shift[j], arr[i].sum_shift[j]) = trav(&arr[i], seq[j]);
  }
  for (int i = 0; i < (1 << 14); i++) fill(dp[i], dp[i] + node, -LINF);
  auto st = trav(root, seq[0]);
  dp[0][st.first->node] = st.second;
  long long ans = -LINF;
  for (int mask = 0; mask < (1 << 14); mask++) {
    if (bit[mask] == seg - 1) {
      for (int cnode = 1; cnode < node; cnode++) uax(ans, dp[mask][cnode]);
    }
    if (bit[mask] >= seg - 1) continue;
    for (int cnode = 1; cnode < node; cnode++) {
      if (dp[mask][cnode] == -LINF) continue;
      for (int let = 0; let < 14; let++) {
        if (mask & (1 << let)) continue;
        int nmask = mask | (1 << let);
        int nnode = arr[cnode].edg[let]->node;
        long long add = arr[nnode].sum_shift[bit[nmask]];
        nnode = arr[nnode].shift[bit[nmask]]->node;
        uax(dp[nmask][nnode], dp[mask][cnode] + add);
      }
    }
  }
  cout << ans;
}
int main() {
  double start = clock();
  cout << fixed << setprecision(20);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  rnd.seed(time(0));
  int t = 1;
  for (int i = 0; i < t; i++) {
    solve();
  }
}

```