#include <bits/stdc++.h>
using namespace std;
template <typename _T>
inline void _DBG(const char *s, _T x) {
  cerr << s << " = " << x << "\n";
}
template <typename _T, typename... args>
void _DBG(const char *s, _T x, args... a) {
  while (*s != ',') cerr << *s++;
  cerr << " = " << x << ',';
  _DBG(s + 1, a...);
}
struct AhoCorasick {
  const int A = 14;
  const int off = 'a';
  int n = 0;
  vector<int> fail, father, letter, ord;
  vector<vector<int>> go;
  vector<long long> value;
  AhoCorasick() {
    father.resize(1, -1);
    letter.resize(1);
    value.resize(1);
    go.resize(1, vector<int>(A));
  }
  void add(const string &s, long long mult = 1) {
    int node = 0;
    for (auto c : s) {
      if (!go[node][c - off]) {
        go[node][c - off] = ++n;
        go.push_back(vector<int>(A));
        fail.push_back(0);
        father.push_back(node);
        letter.push_back(c - off);
        value.push_back(0);
      }
      node = go[node][c - off];
    }
    value[node] += mult;
  }
  void create_automaton() {
    queue<int> Q;
    fail.resize(n + 1);
    Q.push(0);
    while (!Q.empty()) {
      int node = Q.front();
      Q.pop();
      if (node != 0 && father[node] != 0)
        fail[node] = go[fail[father[node]]][letter[node]];
      for (int i = 0; i < A; i++) {
        if (node != 0 && go[node][i] == 0)
          go[node][i] = go[fail[node]][i];
        else if (go[node][i] != 0)
          Q.push(go[node][i]);
      }
    }
  }
  pair<int, long long> read(const string &s, int q0 = 0) {
    long long ans = value[q0];
    for (auto c : s) {
      q0 = go[q0][c - off];
      ans += value[q0];
    }
    return {q0, ans};
  }
};
const int N = 4e5 + 7;
const int A = 14;
const int M = 1007;
const long long INF = 1e18;
AhoCorasick AC;
int m;
long long mult[M];
string str[M];
string cur = "";
void dfs(int v) {
  for (int i = 0; i < m; i++) {
    if ((int)(str[i]).size() <= (int)(cur).size()) {
      bool ok = true;
      for (int j = 0; j < (int)(str[i]).size(); j++) {
        if (str[i][j] != cur[(int)(cur).size() - (int)(str[i]).size() + j]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        AC.value[v] += mult[i];
      }
    }
  }
  for (int i = 0; i < A; i++) {
    if (AC.father[AC.go[v][i]] == v) {
      cur.push_back(i + 'a');
      dfs(AC.go[v][i]);
      cur.pop_back();
    }
  }
}
int n;
string s;
pair<int, long long> whe[A + 1][M];
long long dp[2][M][1 << A];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> str[i] >> mult[i];
    AC.add(str[i], 0);
  }
  AC.create_automaton();
  dfs(0);
  cin >> s;
  s.push_back('?');
  n = (int)(s).size();
  int k = 0;
  string tmp = "";
  for (int i = 0; i < n; i++) {
    if (s[i] == '?') {
      for (int v = 0; v <= AC.n; v++) whe[k][v] = AC.read(tmp, v);
      tmp = "";
      k++;
    } else
      tmp.push_back(s[i]);
  }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j <= AC.n; j++)
      for (int mask = 0; mask < (1 << A); mask++) dp[i][j][mask] = -INF;
  dp[0][whe[0][0].first][0] = whe[0][0].second;
  for (int i = 1; i < k; i++) {
    for (int v = 0; v <= AC.n; v++)
      for (int mask = 0; mask < (1 << A); mask++) dp[i & 1][v][mask] = -INF;
    for (int v = 0; v <= AC.n; v++) {
      for (int mask = 0; mask < (1 << A); mask++) {
        if (__builtin_popcount(mask) != i) continue;
        for (int j = 0; j < A; j++) {
          if ((mask >> j) & 1) {
            auto [u, c] = whe[i][AC.go[v][j]];
            dp[i & 1][u][mask] = max(dp[i & 1][u][mask],
                                     dp[(i - 1) & 1][v][mask ^ (1 << j)] + c);
          }
        }
      }
    }
  }
  long long ans = -INF;
  for (int v = 0; v <= AC.n; v++)
    for (int mask = 0; mask < (1 << A); mask++)
      ans = max(ans, dp[(k - 1) & 1][v][mask]);
  cout << ans << "\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;
template <typename _T>
inline void _DBG(const char *s, _T x) {
  cerr << s << " = " << x << "\n";
}
template <typename _T, typename... args>
void _DBG(const char *s, _T x, args... a) {
  while (*s != ',') cerr << *s++;
  cerr << " = " << x << ',';
  _DBG(s + 1, a...);
}
struct AhoCorasick {
  const int A = 14;
  const int off = 'a';
  int n = 0;
  vector<int> fail, father, letter, ord;
  vector<vector<int>> go;
  vector<long long> value;
  AhoCorasick() {
    father.resize(1, -1);
    letter.resize(1);
    value.resize(1);
    go.resize(1, vector<int>(A));
  }
  void add(const string &s, long long mult = 1) {
    int node = 0;
    for (auto c : s) {
      if (!go[node][c - off]) {
        go[node][c - off] = ++n;
        go.push_back(vector<int>(A));
        fail.push_back(0);
        father.push_back(node);
        letter.push_back(c - off);
        value.push_back(0);
      }
      node = go[node][c - off];
    }
    value[node] += mult;
  }
  void create_automaton() {
    queue<int> Q;
    fail.resize(n + 1);
    Q.push(0);
    while (!Q.empty()) {
      int node = Q.front();
      Q.pop();
      if (node != 0 && father[node] != 0)
        fail[node] = go[fail[father[node]]][letter[node]];
      for (int i = 0; i < A; i++) {
        if (node != 0 && go[node][i] == 0)
          go[node][i] = go[fail[node]][i];
        else if (go[node][i] != 0)
          Q.push(go[node][i]);
      }
    }
  }
  pair<int, long long> read(const string &s, int q0 = 0) {
    long long ans = value[q0];
    for (auto c : s) {
      q0 = go[q0][c - off];
      ans += value[q0];
    }
    return {q0, ans};
  }
};
const int N = 4e5 + 7;
const int A = 14;
const int M = 1007;
const long long INF = 1e18;
AhoCorasick AC;
int m;
long long mult[M];
string str[M];
string cur = "";
void dfs(int v) {
  for (int i = 0; i < m; i++) {
    if ((int)(str[i]).size() <= (int)(cur).size()) {
      bool ok = true;
      for (int j = 0; j < (int)(str[i]).size(); j++) {
        if (str[i][j] != cur[(int)(cur).size() - (int)(str[i]).size() + j]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        AC.value[v] += mult[i];
      }
    }
  }
  for (int i = 0; i < A; i++) {
    if (AC.father[AC.go[v][i]] == v) {
      cur.push_back(i + 'a');
      dfs(AC.go[v][i]);
      cur.pop_back();
    }
  }
}
int n;
string s;
pair<int, long long> whe[A + 1][M];
long long dp[2][M][1 << A];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> str[i] >> mult[i];
    AC.add(str[i], 0);
  }
  AC.create_automaton();
  dfs(0);
  cin >> s;
  s.push_back('?');
  n = (int)(s).size();
  int k = 0;
  string tmp = "";
  for (int i = 0; i < n; i++) {
    if (s[i] == '?') {
      for (int v = 0; v <= AC.n; v++) whe[k][v] = AC.read(tmp, v);
      tmp = "";
      k++;
    } else
      tmp.push_back(s[i]);
  }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j <= AC.n; j++)
      for (int mask = 0; mask < (1 << A); mask++) dp[i][j][mask] = -INF;
  dp[0][whe[0][0].first][0] = whe[0][0].second;
  for (int i = 1; i < k; i++) {
    for (int v = 0; v <= AC.n; v++)
      for (int mask = 0; mask < (1 << A); mask++) dp[i & 1][v][mask] = -INF;
    for (int v = 0; v <= AC.n; v++) {
      for (int mask = 0; mask < (1 << A); mask++) {
        if (__builtin_popcount(mask) != i) continue;
        for (int j = 0; j < A; j++) {
          if ((mask >> j) & 1) {
            auto [u, c] = whe[i][AC.go[v][j]];
            dp[i & 1][u][mask] = max(dp[i & 1][u][mask],
                                     dp[(i - 1) & 1][v][mask ^ (1 << j)] + c);
          }
        }
      }
    }
  }
  long long ans = -INF;
  for (int v = 0; v <= AC.n; v++)
    for (int mask = 0; mask < (1 << A); mask++)
      ans = max(ans, dp[(k - 1) & 1][v][mask]);
  cout << ans << "\n";
  return 0;
}

```