#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
template <class T>
struct RMQ {
  const int STEP_P = 5;
  const int STEP = 1 << STEP_P;
  const vector<T> data;
  const T INF;
  vector<vector<T> > small_powers, group_powers;
  int N;
  RMQ(vector<T> data_, T INF_) : data(data_), INF(INF_) { init(); }
  void init() {
    N = int((data).size());
    small_powers = vector<vector<T> >(STEP_P + 1, vector<T>(N));
    small_powers[0] = data;
    for (int p = (0); p < (STEP_P); p++)
      for (int n = (0); n < (N); n++) {
        small_powers[p + 1][n] =
            min(small_powers[p][n], small_powers[p][min(n + (1 << p), N - 1)]);
      }
    int GN = (N + STEP - 1) / STEP;
    int GP = 1;
    while (GN > (1 << GP)) ++GP;
    group_powers = vector<vector<T> >(GP + 1, vector<T>(GN));
    for (int i = (0); i < (GN); i++)
      group_powers[0][i] = small_powers[STEP_P][i << STEP_P];
    for (int p = (0); p < (GP); p++)
      for (int n = (0); n < (GN); n++) {
        group_powers[p + 1][n] =
            min(group_powers[p][n], group_powers[p][min(n + (1 << p), GN - 1)]);
      }
  }
  int largest_bit(int n) { return 31 - __builtin_clz(max(1, n - 1)); }
  T query(int f, int t) {
    f = max(f, 0);
    t = min(t, N);
    if (f >= t) return INF;
    int p = min(STEP_P, largest_bit(t - f));
    auto res = min(small_powers[p][f], small_powers[p][t - (1 << p)]);
    if (t - f > STEP + STEP) {
      int g_f = f / STEP + 1, g_t = t / STEP;
      p = largest_bit(g_t - g_f);
      res =
          min(res, min(group_powers[p][g_f], group_powers[p][g_t - (1 << p)]));
    }
    return res;
  }
};
template <class T>
struct Suffix_Array {
  vector<T> text;
  vector<int> indices;
  vector<int> lcp;
  Suffix_Array(vector<T> text_) : text(text_) { init(); }
  void init() {
    int n = int((text).size()), N = n + 1, B;
    vector<T> values = text;
    vector<int> order(N);
    sort((values).begin(), (values).end());
    auto fin = unique((values).begin(), (values).end());
    values.resize(B = (int)(fin - values.begin()));
    for (int i = (0); i < (n); i++)
      order[i] = (int)(lower_bound((values).begin(), (values).end(), text[i]) -
                       values.begin() + 1);
    order[N - 1] = 0;
    vector<vector<int> > buckets(++B);
    for (int i = (0); i < (N); i++) buckets[order[i]].push_back(i);
    for (auto it : buckets)
      for (auto i : it) indices.push_back(i);
    int S = 1;
    while (B < N) {
      buckets = vector<vector<int> >(B);
      for (int i = (0); i < (S); i++)
        buckets[order[N - S + i]].push_back(N - S + i);
      for (int i = (0); i < (N); i++)
        if (indices[i] >= S)
          buckets[order[indices[i] - S]].push_back(indices[i] - S);
      indices.clear();
      vector<int> n_order = order;
      B = 0;
      for (auto it : buckets) {
        int last = -2;
        for (auto i : it) {
          indices.push_back(i);
          int b = ((i + S < N) ? order[i + S] : -1);
          if (last != b) {
            last = b;
            B++;
          }
          n_order[i] = B - 1;
        }
      }
      order = n_order;
      S *= 2;
    }
    lcp.resize(n);
    for (int i = 0, K = 0; i < n; ++i, K ? --K : 0) {
      if (order[i] == n) {
        K = 0;
        continue;
      }
      int j = indices[order[i] + 1];
      while (i + K < n && j + K < n && text[i + K] == text[j + K]) ++K;
      lcp[order[i]] = K;
    }
  }
};
string keywords[1024];
int cost[1024];
int start_lo[1024];
int start_hi[1024];
string reference;
string sufstring;
unordered_set<string> relevant_prefixes[16];
unordered_map<string, long long> cost_change[16];
unordered_map<string, long long> dp[16][1 << 14];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int K;
  cin >> K;
  for (int i = (0); i < (K); i++) cin >> keywords[i] >> cost[i];
  cin >> reference;
  int N = int((reference).size());
  {
    ostringstream os;
    os << reference << "#";
    int L = N + 1;
    for (int i = (0); i < (K); i++) {
      start_lo[i] = L;
      os << keywords[i] << "!";
      os << keywords[i] << "|";
      start_hi[i] = L + int((keywords[i]).size()) + 1;
      L += (int((keywords[i]).size()) + 1) * 2;
    }
    sufstring = os.str();
  }
  vector<char> sufstringv((sufstring).begin(), (sufstring).end());
  Suffix_Array<char> sa(sufstringv);
  vector<int> reverse_indices(sa.indices.size(), -1);
  for (int i = (0); i < (int((reverse_indices).size())); i++) {
    assert(sa.indices[i] >= 0 && sa.indices[i] < int((sa.indices).size()));
    assert(reverse_indices[sa.indices[i]] == -1);
    reverse_indices[sa.indices[i]] = i;
  }
  vector<int> count_real_string(int((reverse_indices).size()) + 1, 0);
  for (int i = (0); i < (int((reverse_indices).size())); i++) {
    count_real_string[i + 1] = count_real_string[i];
    if (sa.indices[i] < N) ++count_real_string[i + 1];
  }
  long long res = 0;
  for (int k = (0); k < (K); k++) {
    res +=
        cost[k] * (long long)(count_real_string[reverse_indices[start_hi[k]]] -
                              count_real_string[reverse_indices[start_lo[k]]]);
  }
  vector<int> questionmarks;
  for (int i = (0); i < (N); i++)
    if (reference[i] == '?') questionmarks.push_back(i);
  for (int k = (0); k < (K); k++) {
    int done = 0;
    for (int q = (0); q < (int((questionmarks).size())); q++) {
      int qi = questionmarks[q];
      for (int s = (max(done, qi - int((keywords[k]).size()) + 1));
           s < (min(N - int((keywords[k]).size()) + 1, qi + 1)); s++) {
        done = s + 1;
        ostringstream needed;
        bool ok = true;
        for (int i = (0); i < (int((keywords[k]).size())); i++) {
          if (reference[s + i] == '?') {
            needed << keywords[k][i];
          } else if (reference[s + i] != keywords[k][i]) {
            ok = false;
            break;
          }
        }
        if (ok) {
          string neededs = needed.str();
          cost_change[q + neededs.size()][neededs] += cost[k];
          for (int i = (1); i < (int((neededs).size())); i++)
            relevant_prefixes[q + i].insert(neededs.substr(0, i));
        }
      }
    }
  }
  dp[0][0][""] = res;
  for (int q = (0); q < (int((questionmarks).size())); q++) {
    for (int mask = (0); mask < (1 << 14); mask++)
      for (auto it : dp[q][mask]) {
        auto cur_s = it.first;
        auto cur_v = it.second;
        for (int ii = (0); ii < (14); ii++)
          if (0 == (mask & (1 << ii))) {
            int nmask = mask | (1 << ii);
            string next_s = cur_s + (char)('a' + ii);
            auto next_v = cur_v;
            for (int i = (0); i < (int((next_s).size())); i++) {
              auto sub_s = next_s.substr(i);
              if (cost_change[q + 1].find(sub_s) != cost_change[q + 1].end()) {
                next_v += cost_change[q + 1][sub_s];
              }
            }
            while (int((next_s).size()) > 0 &&
                   relevant_prefixes[q + 1].find(next_s) ==
                       relevant_prefixes[q + 1].end())
              next_s = next_s.substr(1);
            if (dp[q + 1][nmask].find(next_s) == dp[q + 1][nmask].end()) {
              dp[q + 1][nmask][next_s] = next_v;
            } else {
              dp[q + 1][nmask][next_s] = max(dp[q + 1][nmask][next_s], next_v);
            }
          }
      }
  }
  bool first = true;
  for (int mask = (0); mask < (1 << 14); mask++) {
    for (auto it : dp[int((questionmarks).size())][mask]) {
      if (first) {
        first = false;
        res = it.second;
      } else {
        res = max(it.second, res);
      }
    }
  }
  cout << res << endl;
  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 double eps = 1e-9;
template <class T>
struct RMQ {
  const int STEP_P = 5;
  const int STEP = 1 << STEP_P;
  const vector<T> data;
  const T INF;
  vector<vector<T> > small_powers, group_powers;
  int N;
  RMQ(vector<T> data_, T INF_) : data(data_), INF(INF_) { init(); }
  void init() {
    N = int((data).size());
    small_powers = vector<vector<T> >(STEP_P + 1, vector<T>(N));
    small_powers[0] = data;
    for (int p = (0); p < (STEP_P); p++)
      for (int n = (0); n < (N); n++) {
        small_powers[p + 1][n] =
            min(small_powers[p][n], small_powers[p][min(n + (1 << p), N - 1)]);
      }
    int GN = (N + STEP - 1) / STEP;
    int GP = 1;
    while (GN > (1 << GP)) ++GP;
    group_powers = vector<vector<T> >(GP + 1, vector<T>(GN));
    for (int i = (0); i < (GN); i++)
      group_powers[0][i] = small_powers[STEP_P][i << STEP_P];
    for (int p = (0); p < (GP); p++)
      for (int n = (0); n < (GN); n++) {
        group_powers[p + 1][n] =
            min(group_powers[p][n], group_powers[p][min(n + (1 << p), GN - 1)]);
      }
  }
  int largest_bit(int n) { return 31 - __builtin_clz(max(1, n - 1)); }
  T query(int f, int t) {
    f = max(f, 0);
    t = min(t, N);
    if (f >= t) return INF;
    int p = min(STEP_P, largest_bit(t - f));
    auto res = min(small_powers[p][f], small_powers[p][t - (1 << p)]);
    if (t - f > STEP + STEP) {
      int g_f = f / STEP + 1, g_t = t / STEP;
      p = largest_bit(g_t - g_f);
      res =
          min(res, min(group_powers[p][g_f], group_powers[p][g_t - (1 << p)]));
    }
    return res;
  }
};
template <class T>
struct Suffix_Array {
  vector<T> text;
  vector<int> indices;
  vector<int> lcp;
  Suffix_Array(vector<T> text_) : text(text_) { init(); }
  void init() {
    int n = int((text).size()), N = n + 1, B;
    vector<T> values = text;
    vector<int> order(N);
    sort((values).begin(), (values).end());
    auto fin = unique((values).begin(), (values).end());
    values.resize(B = (int)(fin - values.begin()));
    for (int i = (0); i < (n); i++)
      order[i] = (int)(lower_bound((values).begin(), (values).end(), text[i]) -
                       values.begin() + 1);
    order[N - 1] = 0;
    vector<vector<int> > buckets(++B);
    for (int i = (0); i < (N); i++) buckets[order[i]].push_back(i);
    for (auto it : buckets)
      for (auto i : it) indices.push_back(i);
    int S = 1;
    while (B < N) {
      buckets = vector<vector<int> >(B);
      for (int i = (0); i < (S); i++)
        buckets[order[N - S + i]].push_back(N - S + i);
      for (int i = (0); i < (N); i++)
        if (indices[i] >= S)
          buckets[order[indices[i] - S]].push_back(indices[i] - S);
      indices.clear();
      vector<int> n_order = order;
      B = 0;
      for (auto it : buckets) {
        int last = -2;
        for (auto i : it) {
          indices.push_back(i);
          int b = ((i + S < N) ? order[i + S] : -1);
          if (last != b) {
            last = b;
            B++;
          }
          n_order[i] = B - 1;
        }
      }
      order = n_order;
      S *= 2;
    }
    lcp.resize(n);
    for (int i = 0, K = 0; i < n; ++i, K ? --K : 0) {
      if (order[i] == n) {
        K = 0;
        continue;
      }
      int j = indices[order[i] + 1];
      while (i + K < n && j + K < n && text[i + K] == text[j + K]) ++K;
      lcp[order[i]] = K;
    }
  }
};
string keywords[1024];
int cost[1024];
int start_lo[1024];
int start_hi[1024];
string reference;
string sufstring;
unordered_set<string> relevant_prefixes[16];
unordered_map<string, long long> cost_change[16];
unordered_map<string, long long> dp[16][1 << 14];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int K;
  cin >> K;
  for (int i = (0); i < (K); i++) cin >> keywords[i] >> cost[i];
  cin >> reference;
  int N = int((reference).size());
  {
    ostringstream os;
    os << reference << "#";
    int L = N + 1;
    for (int i = (0); i < (K); i++) {
      start_lo[i] = L;
      os << keywords[i] << "!";
      os << keywords[i] << "|";
      start_hi[i] = L + int((keywords[i]).size()) + 1;
      L += (int((keywords[i]).size()) + 1) * 2;
    }
    sufstring = os.str();
  }
  vector<char> sufstringv((sufstring).begin(), (sufstring).end());
  Suffix_Array<char> sa(sufstringv);
  vector<int> reverse_indices(sa.indices.size(), -1);
  for (int i = (0); i < (int((reverse_indices).size())); i++) {
    assert(sa.indices[i] >= 0 && sa.indices[i] < int((sa.indices).size()));
    assert(reverse_indices[sa.indices[i]] == -1);
    reverse_indices[sa.indices[i]] = i;
  }
  vector<int> count_real_string(int((reverse_indices).size()) + 1, 0);
  for (int i = (0); i < (int((reverse_indices).size())); i++) {
    count_real_string[i + 1] = count_real_string[i];
    if (sa.indices[i] < N) ++count_real_string[i + 1];
  }
  long long res = 0;
  for (int k = (0); k < (K); k++) {
    res +=
        cost[k] * (long long)(count_real_string[reverse_indices[start_hi[k]]] -
                              count_real_string[reverse_indices[start_lo[k]]]);
  }
  vector<int> questionmarks;
  for (int i = (0); i < (N); i++)
    if (reference[i] == '?') questionmarks.push_back(i);
  for (int k = (0); k < (K); k++) {
    int done = 0;
    for (int q = (0); q < (int((questionmarks).size())); q++) {
      int qi = questionmarks[q];
      for (int s = (max(done, qi - int((keywords[k]).size()) + 1));
           s < (min(N - int((keywords[k]).size()) + 1, qi + 1)); s++) {
        done = s + 1;
        ostringstream needed;
        bool ok = true;
        for (int i = (0); i < (int((keywords[k]).size())); i++) {
          if (reference[s + i] == '?') {
            needed << keywords[k][i];
          } else if (reference[s + i] != keywords[k][i]) {
            ok = false;
            break;
          }
        }
        if (ok) {
          string neededs = needed.str();
          cost_change[q + neededs.size()][neededs] += cost[k];
          for (int i = (1); i < (int((neededs).size())); i++)
            relevant_prefixes[q + i].insert(neededs.substr(0, i));
        }
      }
    }
  }
  dp[0][0][""] = res;
  for (int q = (0); q < (int((questionmarks).size())); q++) {
    for (int mask = (0); mask < (1 << 14); mask++)
      for (auto it : dp[q][mask]) {
        auto cur_s = it.first;
        auto cur_v = it.second;
        for (int ii = (0); ii < (14); ii++)
          if (0 == (mask & (1 << ii))) {
            int nmask = mask | (1 << ii);
            string next_s = cur_s + (char)('a' + ii);
            auto next_v = cur_v;
            for (int i = (0); i < (int((next_s).size())); i++) {
              auto sub_s = next_s.substr(i);
              if (cost_change[q + 1].find(sub_s) != cost_change[q + 1].end()) {
                next_v += cost_change[q + 1][sub_s];
              }
            }
            while (int((next_s).size()) > 0 &&
                   relevant_prefixes[q + 1].find(next_s) ==
                       relevant_prefixes[q + 1].end())
              next_s = next_s.substr(1);
            if (dp[q + 1][nmask].find(next_s) == dp[q + 1][nmask].end()) {
              dp[q + 1][nmask][next_s] = next_v;
            } else {
              dp[q + 1][nmask][next_s] = max(dp[q + 1][nmask][next_s], next_v);
            }
          }
      }
  }
  bool first = true;
  for (int mask = (0); mask < (1 << 14); mask++) {
    for (auto it : dp[int((questionmarks).size())][mask]) {
      if (first) {
        first = false;
        res = it.second;
      } else {
        res = max(it.second, res);
      }
    }
  }
  cout << res << endl;
  return 0;
}

```