#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const long long inf64 = 1e18;
const int A = 14;
struct Aho {
  struct Node {
    int nxt[A], go[A];
    int par, pch, link;
    int len;
    long long sum;
    Node() : par(-1), pch(-1), link(-1), len(0), sum(0) {
      fill(nxt, nxt + A, -1);
      fill(go, go + A, -1);
    }
  };
  vector<Node> a;
  Aho() { a.emplace_back(); }
  void add_string(const string &s, long long cost) {
    int v = 0;
    for (char c : s) {
      if (a[v].nxt[c] == -1) {
        a[v].nxt[c] = (int)a.size();
        a.emplace_back();
        a.back().par = v;
        a.back().pch = c;
        a.back().len = a[v].len + 1;
      }
      v = a[v].nxt[c];
    }
    a[v].sum += cost;
  }
  int go(int v, int c) {
    if (a[v].go[c] == -1) {
      if (a[v].nxt[c] != -1) {
        a[v].go[c] = a[v].nxt[c];
      } else {
        a[v].go[c] = v ? go(get_link(v), c) : 0;
      }
    }
    return a[v].go[c];
  }
  int get_link(int v) {
    if (a[v].link == -1) {
      if (!v || !a[v].par)
        a[v].link = 0;
      else
        a[v].link = go(get_link(a[v].par), a[v].pch);
    }
    return a[v].link;
  }
  void push_sum() {
    vector<int> vs(a.size());
    for (int i = 0; i < (int)vs.size(); i++) vs[i] = i;
    sort(vs.begin(), vs.end(),
         [&](int v1, int v2) { return a[v1].len < a[v2].len; });
    for (int v : vs) {
      a[v].sum += a[get_link(v)].sum;
    }
  }
};
inline void upd(long long &x, long long y) {
  if (x < y) x = y;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int k;
  cin >> k;
  vector<string> t(k);
  vector<long long> cost(k);
  Aho aho;
  for (int i = 0; i < k; i++) {
    cin >> t[i] >> cost[i];
    for (char &c : t[i]) c -= 'a';
    aho.add_string(t[i], cost[i]);
  }
  aho.push_sum();
  string s;
  cin >> s;
  vector<int> ps = {-1};
  for (int i = 0; i < (int)s.size(); i++) {
    if (s[i] == '?')
      ps.push_back(i);
    else
      s[i] -= 'a';
  }
  ps.push_back((int)s.size());
  int sz = (int)aho.a.size();
  vector<vector<pair<int, long long>>> mem(
      sz, vector<pair<int, long long>>(ps.size()));
  for (int i = 0; i + 1 < (int)ps.size(); i++) {
    int fr = ps[i] + 1;
    int to = ps[i + 1] - 1;
    for (int start = 0; start < sz; start++) {
      long long cur_sum = 0;
      int v = start;
      for (int p = fr; p <= to; p++) {
        v = aho.go(v, s[p]);
        cur_sum += aho.a[v].sum;
      }
      mem[start][i] = {v, cur_sum};
    }
  }
  vector<vector<long long>> dp(sz, vector<long long>(1 << 14, -inf64)), nx;
  dp[0][0] = 0;
  vector<int> cnt_bit(1 << 14);
  for (int i = 0; i < (int)cnt_bit.size(); i++) {
    cnt_bit[i] = __builtin_popcount(i);
  }
  for (int i = 0; i + 2 < (int)ps.size(); i++) {
    nx.assign(sz, vector<long long>(1 << 14, -inf64));
    for (int v = 0; v < sz; v++) {
      int nxt;
      long long score;
      tie(nxt, score) = mem[v][i];
      for (int mask = 0; mask < (1 << 14); mask++) {
        if (cnt_bit[mask] != i) continue;
        for (int c = 0; c < 14; c++) {
          if (((1 << c) & mask)) continue;
          int nxt_mask = mask | (1 << c);
          int to = aho.go(nxt, c);
          long long tmp = score + aho.a[to].sum;
          upd(nx[to][nxt_mask], dp[v][mask] + tmp);
        }
      }
    }
    dp = nx;
  }
  int cnt_q = (int)ps.size() - 2;
  long long res = -inf64;
  for (int mask = 0; mask < (1 << 14); mask++) {
    if (cnt_bit[mask] != cnt_q) continue;
    for (int v = 0; v < sz; v++) {
      int nxt;
      long long score;
      tie(nxt, score) = mem[v][(int)ps.size() - 2];
      upd(res, dp[v][mask] + score);
    }
  }
  cout << res << "\n";
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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 inf = 1e9;
const long long inf64 = 1e18;
const int A = 14;
struct Aho {
  struct Node {
    int nxt[A], go[A];
    int par, pch, link;
    int len;
    long long sum;
    Node() : par(-1), pch(-1), link(-1), len(0), sum(0) {
      fill(nxt, nxt + A, -1);
      fill(go, go + A, -1);
    }
  };
  vector<Node> a;
  Aho() { a.emplace_back(); }
  void add_string(const string &s, long long cost) {
    int v = 0;
    for (char c : s) {
      if (a[v].nxt[c] == -1) {
        a[v].nxt[c] = (int)a.size();
        a.emplace_back();
        a.back().par = v;
        a.back().pch = c;
        a.back().len = a[v].len + 1;
      }
      v = a[v].nxt[c];
    }
    a[v].sum += cost;
  }
  int go(int v, int c) {
    if (a[v].go[c] == -1) {
      if (a[v].nxt[c] != -1) {
        a[v].go[c] = a[v].nxt[c];
      } else {
        a[v].go[c] = v ? go(get_link(v), c) : 0;
      }
    }
    return a[v].go[c];
  }
  int get_link(int v) {
    if (a[v].link == -1) {
      if (!v || !a[v].par)
        a[v].link = 0;
      else
        a[v].link = go(get_link(a[v].par), a[v].pch);
    }
    return a[v].link;
  }
  void push_sum() {
    vector<int> vs(a.size());
    for (int i = 0; i < (int)vs.size(); i++) vs[i] = i;
    sort(vs.begin(), vs.end(),
         [&](int v1, int v2) { return a[v1].len < a[v2].len; });
    for (int v : vs) {
      a[v].sum += a[get_link(v)].sum;
    }
  }
};
inline void upd(long long &x, long long y) {
  if (x < y) x = y;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int k;
  cin >> k;
  vector<string> t(k);
  vector<long long> cost(k);
  Aho aho;
  for (int i = 0; i < k; i++) {
    cin >> t[i] >> cost[i];
    for (char &c : t[i]) c -= 'a';
    aho.add_string(t[i], cost[i]);
  }
  aho.push_sum();
  string s;
  cin >> s;
  vector<int> ps = {-1};
  for (int i = 0; i < (int)s.size(); i++) {
    if (s[i] == '?')
      ps.push_back(i);
    else
      s[i] -= 'a';
  }
  ps.push_back((int)s.size());
  int sz = (int)aho.a.size();
  vector<vector<pair<int, long long>>> mem(
      sz, vector<pair<int, long long>>(ps.size()));
  for (int i = 0; i + 1 < (int)ps.size(); i++) {
    int fr = ps[i] + 1;
    int to = ps[i + 1] - 1;
    for (int start = 0; start < sz; start++) {
      long long cur_sum = 0;
      int v = start;
      for (int p = fr; p <= to; p++) {
        v = aho.go(v, s[p]);
        cur_sum += aho.a[v].sum;
      }
      mem[start][i] = {v, cur_sum};
    }
  }
  vector<vector<long long>> dp(sz, vector<long long>(1 << 14, -inf64)), nx;
  dp[0][0] = 0;
  vector<int> cnt_bit(1 << 14);
  for (int i = 0; i < (int)cnt_bit.size(); i++) {
    cnt_bit[i] = __builtin_popcount(i);
  }
  for (int i = 0; i + 2 < (int)ps.size(); i++) {
    nx.assign(sz, vector<long long>(1 << 14, -inf64));
    for (int v = 0; v < sz; v++) {
      int nxt;
      long long score;
      tie(nxt, score) = mem[v][i];
      for (int mask = 0; mask < (1 << 14); mask++) {
        if (cnt_bit[mask] != i) continue;
        for (int c = 0; c < 14; c++) {
          if (((1 << c) & mask)) continue;
          int nxt_mask = mask | (1 << c);
          int to = aho.go(nxt, c);
          long long tmp = score + aho.a[to].sum;
          upd(nx[to][nxt_mask], dp[v][mask] + tmp);
        }
      }
    }
    dp = nx;
  }
  int cnt_q = (int)ps.size() - 2;
  long long res = -inf64;
  for (int mask = 0; mask < (1 << 14); mask++) {
    if (cnt_bit[mask] != cnt_q) continue;
    for (int v = 0; v < sz; v++) {
      int nxt;
      long long score;
      tie(nxt, score) = mem[v][(int)ps.size() - 2];
      upd(res, dp[v][mask] + score);
    }
  }
  cout << res << "\n";
  return 0;
}

```