#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Karasik {
  struct node {
    int parent;
    char ch;
    bool terminal;
    int link;
    map<char, int> next;
    map<char, int> go;
    int cost_sum;
    bool marked;
    node(int parent, char ch)
        : parent(parent), ch(ch), link(-1), marked(false), cost_sum(0) {}
  };
  const int root = 0;
  vector<node> nodes;
  Karasik(vector<pair<string, int>> &a) {
    nodes.emplace_back(root, 0);
    for (int i = 0; i < a.size(); ++i) {
      add_string(a[i].first, a[i].second);
    }
  }
  void add_string(string &s, int cost) {
    int cur_state = root;
    for (int i = 0; i < s.size(); ++i) {
      if (nodes[cur_state].next.count(s[i])) {
        cur_state = nodes[cur_state].next[s[i]];
      } else {
        nodes[cur_state].next[s[i]] = nodes.size();
        nodes.emplace_back(cur_state, s[i]);
        cur_state = nodes.size() - 1;
      }
    }
    nodes[cur_state].terminal = true;
    nodes[cur_state].cost_sum += cost;
  }
  int get_link(int state) {
    if (nodes[state].link == -1) {
      if (state == root || nodes[state].parent == root) {
        nodes[state].link = root;
      } else {
        nodes[state].link = go(get_link(nodes[state].parent), nodes[state].ch);
      }
    }
    return nodes[state].link;
  }
  int go(int state, char c) {
    if (!nodes[state].go.count(c)) {
      if (nodes[state].next.count(c)) {
        nodes[state].go[c] = nodes[state].next[c];
      } else {
        nodes[state].go[c] = state == root ? root : go(get_link(state), c);
      }
    }
    return nodes[state].go[c];
  }
  int state;
  void reset_state(int new_state = -1) {
    if (new_state == -1) {
      state = root;
    } else {
      state = new_state;
    }
  }
  int visit_terminal_links(int state) {
    if (!nodes[state].marked) {
      nodes[state].marked = true;
      nodes[state].cost_sum += visit_terminal_links(get_link(state));
    }
    return nodes[state].cost_sum;
  }
  int move_state(char c) {
    state = go(state, c);
    return visit_terminal_links(state);
  }
};
ll solve(vector<pair<string, int>> &sc, string &s) {
  const int maxq = 14;
  vector<int> qpos;
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == '?') {
      qpos.push_back(i);
    }
  }
  qpos.push_back(s.size());
  Karasik karasik(sc);
  karasik.reset_state();
  ll left_sum = 0;
  for (int i = 0; i < qpos[0]; ++i) {
    left_sum += karasik.move_state(s[i]);
  }
  int left_state = karasik.state;
  const int qsz = qpos.size();
  const int state_sz = karasik.nodes.size();
  const int mask_sz = (1 << maxq);
  const ll INF = 1e16;
  vector<vector<vector<ll>>> dp(
      2, vector<vector<ll>>(state_sz, vector<ll>(mask_sz, -INF)));
  dp[0][left_state][0] = left_sum;
  auto update_max = [](ll &res, ll candidate) { res = max(res, candidate); };
  for (int i = 0; i + 1 < qsz; ++i) {
    vector<pair<int, ll>> next_state(state_sz);
    int len = qpos[i + 1] - qpos[i] - 1;
    vector<ll> mem_values(len), mem_suff_sum(len + 1);
    vector<int> mem_states(len);
    for (int j = 0, first_try = true; j < state_sz; ++j) {
      ll sum = 0;
      karasik.reset_state(j);
      for (int idx = qpos[i] + 1, irel = 0; idx < qpos[i + 1]; ++idx, ++irel) {
        ll cur = karasik.move_state(s[idx]);
        if (first_try) {
          mem_values[irel] = cur;
          mem_states[irel] = karasik.state;
        } else if (mem_states[irel] == karasik.state) {
          sum += mem_suff_sum[irel];
          karasik.reset_state(mem_states.back());
          break;
        }
        sum += cur;
      }
      if (first_try) {
        for (int irel = len - 1; irel >= 0; --irel) {
          mem_suff_sum[irel] = mem_suff_sum[irel + 1] + mem_values[irel];
        }
        first_try = false;
      }
      next_state[j] = {karasik.state, sum};
    }
    for (int j = 0; j < state_sz; ++j) {
      for (int mask = 0; mask < mask_sz; ++mask) {
        if (dp[0][j][mask] == -INF) continue;
        for (int sym = 0; sym < maxq; ++sym) {
          if (mask & (1 << sym)) continue;
          karasik.reset_state(j);
          ll sum = karasik.move_state('a' + sym);
          int state = karasik.state;
          int trans_state = next_state[state].first;
          sum += next_state[state].second;
          update_max(dp[1][trans_state][mask | (1 << sym)],
                     dp[0][j][mask] + sum);
        }
      }
    }
    swap(dp[0], dp[1]);
    for (int j = 0; j < state_sz; ++j) {
      for (int mask = 0; mask < mask_sz; ++mask) {
        dp[1][j][mask] = -INF;
      }
    }
  }
  ll res = -INF;
  for (int j = 0; j < state_sz; ++j) {
    for (int mask = 0; mask < mask_sz; ++mask) {
      res = max(res, dp[0][j][mask]);
    }
  }
  return res;
}
ll solve_slow(vector<pair<string, int>> &sc, string &s) {
  auto check_string = [&](string &s) {
    ll res = 0;
    for (int i = 0; i < s.size(); ++i) {
      for (auto &[word, cost] : sc) {
        if (s.substr(i, word.size()) == word) {
          res += cost;
        }
      }
    }
    return res;
  };
  vector<int> qpos;
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == '?') {
      qpos.push_back(i);
    }
  }
  const int maxsym = 10;
  ll res = -1e16;
  string cur = s;
  function<void(int, int)> rec = [&](int idx, int used) {
    if (idx == qpos.size()) {
      res = max(res, check_string(cur));
    } else {
      for (int i = 0; i < maxsym; ++i) {
        if (!(used & (1 << i))) {
          cur[qpos[idx]] = 'a' + i;
          rec(idx + 1, used | (1 << i));
        }
      }
    }
  };
  rec(0, 0);
  return res;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int k;
  while (cin >> k) {
    vector<pair<string, int>> sc(k);
    for (auto &[s, c] : sc) cin >> s >> c;
    string s;
    cin >> s;
    cout << solve(sc, s) << "\n";
    break;
  }
  return 0;
  for (int z = 0; z < 100; ++z) {
    mt19937 rng(z);
    int k = 5;
    int n = 7;
    int maxwordlen = 5;
    int maxsym = 2;
    int maxcost = 10;
    string s(n, 'a');
    vector<pair<string, int>> a(k);
    for (auto &e : s) e += rng() % maxsym;
    for (auto &[s, c] : a) {
      int len = 1 + rng() % maxwordlen;
      c = -maxcost + rng() % (2 * maxcost + 1);
      s.resize(len, 'a');
      for (auto &e : s) e += rng() % maxsym;
    }
    int qm = min<int>(n, rng() % 5);
    vector<int> shuf(n);
    iota(shuf.begin(), shuf.end(), 0);
    shuffle(shuf.begin(), shuf.end(), rng);
    for (int i = 0; i < qm; ++i) s[shuf[i]] = '?';
    auto slow = solve_slow(a, s);
    auto fast = solve(a, s);
    if (slow != fast) {
      cout << z << endl;
      cout << k << endl;
      for (auto &[s, c] : a) cout << s << " " << c << endl;
      cout << s << endl;
      cout << "slow: " << slow << endl;
      cout << "fast: " << fast << endl;
      break;
    }
  }
}

### Prompt

Your task is to create 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;
using ll = long long;
struct Karasik {
  struct node {
    int parent;
    char ch;
    bool terminal;
    int link;
    map<char, int> next;
    map<char, int> go;
    int cost_sum;
    bool marked;
    node(int parent, char ch)
        : parent(parent), ch(ch), link(-1), marked(false), cost_sum(0) {}
  };
  const int root = 0;
  vector<node> nodes;
  Karasik(vector<pair<string, int>> &a) {
    nodes.emplace_back(root, 0);
    for (int i = 0; i < a.size(); ++i) {
      add_string(a[i].first, a[i].second);
    }
  }
  void add_string(string &s, int cost) {
    int cur_state = root;
    for (int i = 0; i < s.size(); ++i) {
      if (nodes[cur_state].next.count(s[i])) {
        cur_state = nodes[cur_state].next[s[i]];
      } else {
        nodes[cur_state].next[s[i]] = nodes.size();
        nodes.emplace_back(cur_state, s[i]);
        cur_state = nodes.size() - 1;
      }
    }
    nodes[cur_state].terminal = true;
    nodes[cur_state].cost_sum += cost;
  }
  int get_link(int state) {
    if (nodes[state].link == -1) {
      if (state == root || nodes[state].parent == root) {
        nodes[state].link = root;
      } else {
        nodes[state].link = go(get_link(nodes[state].parent), nodes[state].ch);
      }
    }
    return nodes[state].link;
  }
  int go(int state, char c) {
    if (!nodes[state].go.count(c)) {
      if (nodes[state].next.count(c)) {
        nodes[state].go[c] = nodes[state].next[c];
      } else {
        nodes[state].go[c] = state == root ? root : go(get_link(state), c);
      }
    }
    return nodes[state].go[c];
  }
  int state;
  void reset_state(int new_state = -1) {
    if (new_state == -1) {
      state = root;
    } else {
      state = new_state;
    }
  }
  int visit_terminal_links(int state) {
    if (!nodes[state].marked) {
      nodes[state].marked = true;
      nodes[state].cost_sum += visit_terminal_links(get_link(state));
    }
    return nodes[state].cost_sum;
  }
  int move_state(char c) {
    state = go(state, c);
    return visit_terminal_links(state);
  }
};
ll solve(vector<pair<string, int>> &sc, string &s) {
  const int maxq = 14;
  vector<int> qpos;
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == '?') {
      qpos.push_back(i);
    }
  }
  qpos.push_back(s.size());
  Karasik karasik(sc);
  karasik.reset_state();
  ll left_sum = 0;
  for (int i = 0; i < qpos[0]; ++i) {
    left_sum += karasik.move_state(s[i]);
  }
  int left_state = karasik.state;
  const int qsz = qpos.size();
  const int state_sz = karasik.nodes.size();
  const int mask_sz = (1 << maxq);
  const ll INF = 1e16;
  vector<vector<vector<ll>>> dp(
      2, vector<vector<ll>>(state_sz, vector<ll>(mask_sz, -INF)));
  dp[0][left_state][0] = left_sum;
  auto update_max = [](ll &res, ll candidate) { res = max(res, candidate); };
  for (int i = 0; i + 1 < qsz; ++i) {
    vector<pair<int, ll>> next_state(state_sz);
    int len = qpos[i + 1] - qpos[i] - 1;
    vector<ll> mem_values(len), mem_suff_sum(len + 1);
    vector<int> mem_states(len);
    for (int j = 0, first_try = true; j < state_sz; ++j) {
      ll sum = 0;
      karasik.reset_state(j);
      for (int idx = qpos[i] + 1, irel = 0; idx < qpos[i + 1]; ++idx, ++irel) {
        ll cur = karasik.move_state(s[idx]);
        if (first_try) {
          mem_values[irel] = cur;
          mem_states[irel] = karasik.state;
        } else if (mem_states[irel] == karasik.state) {
          sum += mem_suff_sum[irel];
          karasik.reset_state(mem_states.back());
          break;
        }
        sum += cur;
      }
      if (first_try) {
        for (int irel = len - 1; irel >= 0; --irel) {
          mem_suff_sum[irel] = mem_suff_sum[irel + 1] + mem_values[irel];
        }
        first_try = false;
      }
      next_state[j] = {karasik.state, sum};
    }
    for (int j = 0; j < state_sz; ++j) {
      for (int mask = 0; mask < mask_sz; ++mask) {
        if (dp[0][j][mask] == -INF) continue;
        for (int sym = 0; sym < maxq; ++sym) {
          if (mask & (1 << sym)) continue;
          karasik.reset_state(j);
          ll sum = karasik.move_state('a' + sym);
          int state = karasik.state;
          int trans_state = next_state[state].first;
          sum += next_state[state].second;
          update_max(dp[1][trans_state][mask | (1 << sym)],
                     dp[0][j][mask] + sum);
        }
      }
    }
    swap(dp[0], dp[1]);
    for (int j = 0; j < state_sz; ++j) {
      for (int mask = 0; mask < mask_sz; ++mask) {
        dp[1][j][mask] = -INF;
      }
    }
  }
  ll res = -INF;
  for (int j = 0; j < state_sz; ++j) {
    for (int mask = 0; mask < mask_sz; ++mask) {
      res = max(res, dp[0][j][mask]);
    }
  }
  return res;
}
ll solve_slow(vector<pair<string, int>> &sc, string &s) {
  auto check_string = [&](string &s) {
    ll res = 0;
    for (int i = 0; i < s.size(); ++i) {
      for (auto &[word, cost] : sc) {
        if (s.substr(i, word.size()) == word) {
          res += cost;
        }
      }
    }
    return res;
  };
  vector<int> qpos;
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == '?') {
      qpos.push_back(i);
    }
  }
  const int maxsym = 10;
  ll res = -1e16;
  string cur = s;
  function<void(int, int)> rec = [&](int idx, int used) {
    if (idx == qpos.size()) {
      res = max(res, check_string(cur));
    } else {
      for (int i = 0; i < maxsym; ++i) {
        if (!(used & (1 << i))) {
          cur[qpos[idx]] = 'a' + i;
          rec(idx + 1, used | (1 << i));
        }
      }
    }
  };
  rec(0, 0);
  return res;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int k;
  while (cin >> k) {
    vector<pair<string, int>> sc(k);
    for (auto &[s, c] : sc) cin >> s >> c;
    string s;
    cin >> s;
    cout << solve(sc, s) << "\n";
    break;
  }
  return 0;
  for (int z = 0; z < 100; ++z) {
    mt19937 rng(z);
    int k = 5;
    int n = 7;
    int maxwordlen = 5;
    int maxsym = 2;
    int maxcost = 10;
    string s(n, 'a');
    vector<pair<string, int>> a(k);
    for (auto &e : s) e += rng() % maxsym;
    for (auto &[s, c] : a) {
      int len = 1 + rng() % maxwordlen;
      c = -maxcost + rng() % (2 * maxcost + 1);
      s.resize(len, 'a');
      for (auto &e : s) e += rng() % maxsym;
    }
    int qm = min<int>(n, rng() % 5);
    vector<int> shuf(n);
    iota(shuf.begin(), shuf.end(), 0);
    shuffle(shuf.begin(), shuf.end(), rng);
    for (int i = 0; i < qm; ++i) s[shuf[i]] = '?';
    auto slow = solve_slow(a, s);
    auto fast = solve(a, s);
    if (slow != fast) {
      cout << z << endl;
      cout << k << endl;
      for (auto &[s, c] : a) cout << s << " " << c << endl;
      cout << s << endl;
      cout << "slow: " << slow << endl;
      cout << "fast: " << fast << endl;
      break;
    }
  }
}

```