#include <bits/stdc++.h>
using namespace std;
const long long M = 2e3 + 10;
const long long K = 14;
struct node {
  long long par = -1, link = -1, elink = -1;
  char pch;
  bool leaf = false, mark = false;
  long long val = 0;
  vector<long long> next, go;
  node(long long par = -1, char ch = '$')
      : par(par), pch(ch), next(K, -1), go(K, -1) {}
};
class Aho {
 public:
  vector<node> t;
  Aho() { t = vector<node>(1); }
  void add(const string& s, long long cost) {
    long long u = 0;
    for (char ch : s) {
      long long c = ch - 'a';
      if (t[u].next[c] < 0) {
        t[u].next[c] = (long long)t.size();
        t.emplace_back(u, ch);
      }
      u = t[u].next[c];
    }
    t[u].leaf = true;
    t[u].val += cost;
  }
  long long get_elink(long long u) {
    if (t[u].elink < 0) {
      long long v = get_link(u);
      if (!u or !v)
        t[u].elink = 0;
      else
        t[u].elink = t[v].leaf ? v : get_elink(v);
    }
    return t[u].elink;
  }
  long long get_link(long long u) {
    if (t[u].link < 0) {
      t[u].link = (!u or !t[u].par) ? 0 : go(get_link(t[u].par), t[u].pch);
    }
    return t[u].link;
  }
  long long go(long long u, char ch) {
    long long c = ch - 'a';
    if (t[u].go[c] < 0) {
      t[u].go[c] =
          (t[u].next[c] != -1) ? t[u].next[c] : (!u ? 0 : go(get_link(u), ch));
    }
    return t[u].go[c];
  }
  long long process(long long u) {
    if (t[u].mark) return t[u].val;
    t[u].mark = true;
    return t[u].val += process(get_elink(u));
  }
  void process() {
    for (long long u = 0; u < (long long)t.size(); ++u) {
      if (!t[u].mark) process(u);
    }
  }
  vector<long long> get(const string& s) {
    long long n = (long long)(s).size(), u = 0;
    vector<long long> cnt(n, 0);
    for (long long i = 0; i < n; ++i) {
      u = go(u, s[i]);
      cnt[i] = t[u].val;
    }
    return cnt;
  }
};
string s;
Aho at;
long long dp[1 << K][M];
long long to[M][K], val[M][K];
long long T, N;
long long f(long long mask, long long u) {
  long long i = __builtin_popcount(mask);
  if (i >= T) return 0;
  long long& ans = dp[mask][u];
  if (ans != -(long long)(1e18)) return ans;
  ans = -(long long)(1e18) / 10;
  for (long long j = 0; j < K; ++j) {
    if (mask & (1 << j)) continue;
    long long v = at.go(u, (char)(j + 'a'));
    ans = max(ans, f(mask | (1 << j), to[v][i]) + val[v][i]);
  }
  return ans;
}
pair<long long, long long> get(long long u, const string& s) {
  long long cost = at.t[u].val;
  for (char ch : s) {
    u = at.go(u, ch);
    cost += at.t[u].val;
  }
  return {cost, u};
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long k;
  cin >> k;
  for (long long i = 0; i < k; ++i) {
    string t;
    cin >> t;
    long long cost;
    cin >> cost;
    at.add(t, cost);
  }
  at.process();
  N = (long long)(at.t).size();
  cin >> s;
  for (long long i = 0; i < (long long)(s).size(); ++i) T += s[i] == '?';
  string now;
  for (long long i = 0; i < (long long)(s).size(); ++i) {
    if (s[i] == '?') break;
    now += s[i];
  }
  auto [rem, u] = get(0, now);
  vector<string> V;
  string pev;
  for (long long i = (long long)(now).size() + 1; i < (long long)(s).size();
       ++i) {
    if (s[i] == '?')
      V.push_back(pev), pev = "";
    else
      pev += s[i];
  }
  V.push_back(pev);
  for (long long i = 0; i < N; ++i) {
    for (long long j = 0; j < (long long)(V).size(); ++j) {
      auto [x, y] = get(i, V[j]);
      val[i][j] = x, to[i][j] = y;
    }
  }
  for (long long mask = 0; mask < 1 << K; ++mask)
    for (long long u = 0; u < N; ++u) dp[mask][u] = -(long long)(1e18);
  cout << rem + f(0, u);
  return 0;
}

### 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>
using namespace std;
const long long M = 2e3 + 10;
const long long K = 14;
struct node {
  long long par = -1, link = -1, elink = -1;
  char pch;
  bool leaf = false, mark = false;
  long long val = 0;
  vector<long long> next, go;
  node(long long par = -1, char ch = '$')
      : par(par), pch(ch), next(K, -1), go(K, -1) {}
};
class Aho {
 public:
  vector<node> t;
  Aho() { t = vector<node>(1); }
  void add(const string& s, long long cost) {
    long long u = 0;
    for (char ch : s) {
      long long c = ch - 'a';
      if (t[u].next[c] < 0) {
        t[u].next[c] = (long long)t.size();
        t.emplace_back(u, ch);
      }
      u = t[u].next[c];
    }
    t[u].leaf = true;
    t[u].val += cost;
  }
  long long get_elink(long long u) {
    if (t[u].elink < 0) {
      long long v = get_link(u);
      if (!u or !v)
        t[u].elink = 0;
      else
        t[u].elink = t[v].leaf ? v : get_elink(v);
    }
    return t[u].elink;
  }
  long long get_link(long long u) {
    if (t[u].link < 0) {
      t[u].link = (!u or !t[u].par) ? 0 : go(get_link(t[u].par), t[u].pch);
    }
    return t[u].link;
  }
  long long go(long long u, char ch) {
    long long c = ch - 'a';
    if (t[u].go[c] < 0) {
      t[u].go[c] =
          (t[u].next[c] != -1) ? t[u].next[c] : (!u ? 0 : go(get_link(u), ch));
    }
    return t[u].go[c];
  }
  long long process(long long u) {
    if (t[u].mark) return t[u].val;
    t[u].mark = true;
    return t[u].val += process(get_elink(u));
  }
  void process() {
    for (long long u = 0; u < (long long)t.size(); ++u) {
      if (!t[u].mark) process(u);
    }
  }
  vector<long long> get(const string& s) {
    long long n = (long long)(s).size(), u = 0;
    vector<long long> cnt(n, 0);
    for (long long i = 0; i < n; ++i) {
      u = go(u, s[i]);
      cnt[i] = t[u].val;
    }
    return cnt;
  }
};
string s;
Aho at;
long long dp[1 << K][M];
long long to[M][K], val[M][K];
long long T, N;
long long f(long long mask, long long u) {
  long long i = __builtin_popcount(mask);
  if (i >= T) return 0;
  long long& ans = dp[mask][u];
  if (ans != -(long long)(1e18)) return ans;
  ans = -(long long)(1e18) / 10;
  for (long long j = 0; j < K; ++j) {
    if (mask & (1 << j)) continue;
    long long v = at.go(u, (char)(j + 'a'));
    ans = max(ans, f(mask | (1 << j), to[v][i]) + val[v][i]);
  }
  return ans;
}
pair<long long, long long> get(long long u, const string& s) {
  long long cost = at.t[u].val;
  for (char ch : s) {
    u = at.go(u, ch);
    cost += at.t[u].val;
  }
  return {cost, u};
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long k;
  cin >> k;
  for (long long i = 0; i < k; ++i) {
    string t;
    cin >> t;
    long long cost;
    cin >> cost;
    at.add(t, cost);
  }
  at.process();
  N = (long long)(at.t).size();
  cin >> s;
  for (long long i = 0; i < (long long)(s).size(); ++i) T += s[i] == '?';
  string now;
  for (long long i = 0; i < (long long)(s).size(); ++i) {
    if (s[i] == '?') break;
    now += s[i];
  }
  auto [rem, u] = get(0, now);
  vector<string> V;
  string pev;
  for (long long i = (long long)(now).size() + 1; i < (long long)(s).size();
       ++i) {
    if (s[i] == '?')
      V.push_back(pev), pev = "";
    else
      pev += s[i];
  }
  V.push_back(pev);
  for (long long i = 0; i < N; ++i) {
    for (long long j = 0; j < (long long)(V).size(); ++j) {
      auto [x, y] = get(i, V[j]);
      val[i][j] = x, to[i][j] = y;
    }
  }
  for (long long mask = 0; mask < 1 << K; ++mask)
    for (long long u = 0; u < N; ++u) dp[mask][u] = -(long long)(1e18);
  cout << rem + f(0, u);
  return 0;
}

```