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
#include <bits/stdc++.h>
using namespace std;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
  cin.exceptions(ios::failbit);
}
static constexpr int ALPHA = 14;
struct node {
  char c = '\0';
  node *children[ALPHA] = {};
  node *advanced[ALPHA] = {};
  node *fail = nullptr;
  long long cost = 0;
  node *get(char c) const;
  node *create(char c);
  node *advance(char c);
};
static vector<node> nodes;
static node *root;
node *node::get(char c) const { return children[c - 'a']; }
node *node::create(char c) {
  node *s = get(c);
  if (s == nullptr) {
    nodes.emplace_back();
    s = &nodes.back();
    s->c = c;
    children[c - 'a'] = s;
  }
  return s;
}
node *node::advance(char c) {
  node *&ans = advanced[c - 'a'];
  if (ans) return ans;
  node *p = this;
  node *q;
  while (p && !(q = p->get(c))) p = p->fail;
  if (p == nullptr)
    return ans = root;
  else
    return ans = q;
}
struct transition {
  node *trg;
  long long cost;
};
int main(int argc, const char **argv) {
  redirect(argc, argv);
  nodes.reserve(2000);
  nodes.emplace_back();
  root = &nodes[0];
  int K;
  cin >> K;
  vector<string> t(K);
  for (int i = 0; i < K; i++) {
    long long cost;
    cin >> t[i] >> cost;
    node *cur = root;
    for (char c : t[i]) cur = cur->create(c);
    cur->cost += cost;
  }
  string S;
  cin >> S;
  vector<int> qs{-1};
  for (int i = 0; i < ((long long)(S).size()); i++)
    if (S[i] == '?') qs.push_back(i);
  qs.push_back(((long long)(S).size()));
  vector<node *> lvl{root};
  while (!lvl.empty()) {
    vector<node *> lvl2;
    for (node *old : lvl)
      for (node *p : old->children) {
        if (!p) continue;
        lvl2.push_back(p);
        node *f = old->fail;
        while (f && !f->get(p->c)) f = f->fail;
        p->fail = f ? f->get(p->c) : root;
        p->cost += p->fail->cost;
      }
    lvl = move(lvl2);
  }
  vector<vector<transition>> trans(
      ((long long)(qs).size()) - 1,
      vector<transition>(((long long)(nodes).size())));
  for (int i = 0; i < ((long long)(qs).size()) - 1; i++) {
    for (int j = 0; j < ((long long)(nodes).size()); j++) {
      node *cur = &nodes[j];
      long long cost = 0;
      for (int k = qs[i] + 1; k < qs[i + 1]; k++) {
        cur = cur->advance(S[k]);
        cost += cur->cost;
      }
      trans[i][j] = transition{cur, cost};
    }
    cerr << '.' << flush;
  }
  cerr << '\n';
  vector<vector<long long>> dp(
      1 << ALPHA,
      vector<long long>(((long long)(nodes).size()), LLONG_MIN / 2));
  dp[0][0] = 0;
  for (int i = 0; i < ((long long)(qs).size()) - 1; i++) {
    vector<vector<long long>> dp2(
        1 << ALPHA,
        vector<long long>(((long long)(nodes).size()), LLONG_MIN / 2));
    for (int mask = 0; mask < (1 << ALPHA); mask++)
      if (__builtin_popcount(mask) == max(0, i - 1))
        for (int nxt = 0; nxt < ALPHA; nxt++)
          if (!(mask & (1 << nxt)))
            for (int state = 0; state < ((long long)(nodes).size()); state++) {
              long long cost = dp[mask][state];
              if (cost <= LLONG_MIN / 2) continue;
              node *cur = &nodes[state];
              int nmask = mask;
              if (i > 0) {
                cur = cur->advance('a' + nxt);
                cost += cur->cost;
                nmask |= 1 << nxt;
              }
              const auto &t = trans[i][cur - &nodes[0]];
              cur = t.trg;
              cost += t.cost;
              auto &d = dp2[nmask][cur - &nodes[0]];
              d = max(d, cost);
            }
    dp = move(dp2);
    cerr << '+' << flush;
  }
  cerr << '\n';
  long long ans = LLONG_MIN;
  for (int mask = 0; mask < (1 << ALPHA); mask++)
    ans = max(ans, *max_element(begin(dp[mask]), end(dp[mask])));
  cout << ans << '\n';
  return 0;
}
