#include <bits/stdc++.h>
using namespace std;
const double PI = 3.1415926535897932384626433832795;
const long long INF = 1LL << 62;
const long long MINF = -1LL << 62;
template <typename T>
T getint() {
  T val = 0;
  char c;
  bool neg = false;
  while ((c = getchar()) && !(c >= '0' && c <= '9')) {
    neg |= c == '-';
  }
  do {
    val = (val * 10) + c - '0';
  } while ((c = getchar()) && (c >= '0' && c <= '9'));
  return val * (neg ? -1 : 1);
}
struct node {
  int sub[14];
  int go[14];
  int par;
  int par_c;
  int link;
  bool veg;
  long long sum = 0;
  bool fixed;
  node() {
    memset(sub, -1, sizeof sub);
    memset(go, -1, sizeof go);
    link = -1;
    veg = false;
  }
};
node tr[2000];
int ind = 1;
void add_str(string x, int cost) {
  int akt = 0;
  for (auto i : x) {
    if (tr[akt].sub[i - 'a'] == -1) {
      tr[akt].sub[i - 'a'] = ind++;
      tr[tr[akt].sub[i - 'a']].par = akt;
      tr[tr[akt].sub[i - 'a']].par_c = i - 'a';
    }
    akt = tr[akt].sub[i - 'a'];
  }
  tr[akt].veg = 1;
  tr[akt].sum += cost;
}
int get_link(int);
int get_go(int x, char c) {
  if (tr[x].go[c - 'a'] != -1) return tr[x].go[c - 'a'];
  if (tr[x].sub[c - 'a'] != -1) return tr[x].go[c - 'a'] = tr[x].sub[c - 'a'];
  if (x == 0) return tr[x].go[c - 'a'] = 0;
  return tr[x].go[c - 'a'] = get_go(get_link(x), c);
}
int get_link(int x) {
  if (tr[x].link != -1) return tr[x].link;
  if (tr[x].par == 0 || x == 0) return tr[x].link = 0;
  return tr[x].link = get_go(get_link(tr[x].par), tr[x].par_c + 'a');
}
void fix(int x) {
  if (x == 0 || tr[x].fixed) return;
  tr[x].fixed = 1;
  fix(get_link(x));
  tr[x].sum += tr[get_link(x)].sum;
}
long long dp[1111][1 << 14];
bool calced[1111][1 << 14];
int qmarks = 0;
int pos[15];
string s;
long long pre_calc[1111][16];
long long uj_all[1111][16];
bool pre_calced[1111][16];
int pre_mask[1 << 14];
int van = 0;
long long calc(int st, int mask) {
  if (calced[st][mask]) return dp[st][mask];
  int ith = pre_mask[mask];
  if (ith == qmarks) {
    if (pre_calced[st][ith]) return pre_calc[st][ith];
    long long res = 0;
    int bef = st;
    for (int i = pos[ith]; i < (int)(s).size(); ++i) {
      if (s[i] != '?') {
        st = get_go(st, s[i]);
        res += tr[st].sum;
      }
    }
    pre_calc[bef][ith] = res;
    pre_calced[bef][ith] = 1;
    calced[bef][mask] = 1;
    return dp[bef][mask] = res;
  }
  int bef = st;
  long long pre = 0;
  if (!pre_calced[st][ith]) {
    int elotte = st;
    for (int i = pos[ith]; i < pos[ith + 1]; i++) {
      if (s[i] != '?') {
        st = get_go(st, s[i]);
        pre += tr[st].sum;
      }
    }
    pre_calc[elotte][ith] = pre;
    pre_calced[elotte][ith] = 1;
    uj_all[elotte][ith] = st;
  } else {
    pre = pre_calc[st][ith];
    st = uj_all[st][ith];
  }
  long long ans = -1LL << 60;
  for (int j = 0; j < 14; ++j) {
    if (((1 << j) & mask) == 0) {
      int kovi = get_go(st, j + 'a');
      ans = max(ans, calc(kovi, mask | (1 << j)) + pre + tr[kovi].sum);
    }
  }
  calced[bef][mask] = 1;
  return dp[bef][mask] = ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int i = 0; i < (1 << 14); ++i) pre_mask[i] = __builtin_popcount(i);
  int k;
  cin >> k;
  for (int i = 0; i < k; ++i) {
    string t;
    cin >> t;
    int cost;
    cin >> cost;
    add_str(t, cost);
  }
  for (int i = 0; i < ind; ++i) fix(i);
  cin >> s;
  int idx = 0;
  for (auto i : s) {
    qmarks += i == '?';
    if (i == '?') {
      pos[qmarks] = idx;
    }
    idx++;
  }
  if (qmarks == 0) {
    int akt = 0;
    long long ans = 0;
    for (auto i : s) {
      akt = get_go(akt, i);
      ans += tr[akt].sum;
    }
    cout << ans << "\n";
  } else {
    cout << calc(0, 0) << "\n";
  }
  return 0;
}

### Prompt

Your challenge is to write 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 double PI = 3.1415926535897932384626433832795;
const long long INF = 1LL << 62;
const long long MINF = -1LL << 62;
template <typename T>
T getint() {
  T val = 0;
  char c;
  bool neg = false;
  while ((c = getchar()) && !(c >= '0' && c <= '9')) {
    neg |= c == '-';
  }
  do {
    val = (val * 10) + c - '0';
  } while ((c = getchar()) && (c >= '0' && c <= '9'));
  return val * (neg ? -1 : 1);
}
struct node {
  int sub[14];
  int go[14];
  int par;
  int par_c;
  int link;
  bool veg;
  long long sum = 0;
  bool fixed;
  node() {
    memset(sub, -1, sizeof sub);
    memset(go, -1, sizeof go);
    link = -1;
    veg = false;
  }
};
node tr[2000];
int ind = 1;
void add_str(string x, int cost) {
  int akt = 0;
  for (auto i : x) {
    if (tr[akt].sub[i - 'a'] == -1) {
      tr[akt].sub[i - 'a'] = ind++;
      tr[tr[akt].sub[i - 'a']].par = akt;
      tr[tr[akt].sub[i - 'a']].par_c = i - 'a';
    }
    akt = tr[akt].sub[i - 'a'];
  }
  tr[akt].veg = 1;
  tr[akt].sum += cost;
}
int get_link(int);
int get_go(int x, char c) {
  if (tr[x].go[c - 'a'] != -1) return tr[x].go[c - 'a'];
  if (tr[x].sub[c - 'a'] != -1) return tr[x].go[c - 'a'] = tr[x].sub[c - 'a'];
  if (x == 0) return tr[x].go[c - 'a'] = 0;
  return tr[x].go[c - 'a'] = get_go(get_link(x), c);
}
int get_link(int x) {
  if (tr[x].link != -1) return tr[x].link;
  if (tr[x].par == 0 || x == 0) return tr[x].link = 0;
  return tr[x].link = get_go(get_link(tr[x].par), tr[x].par_c + 'a');
}
void fix(int x) {
  if (x == 0 || tr[x].fixed) return;
  tr[x].fixed = 1;
  fix(get_link(x));
  tr[x].sum += tr[get_link(x)].sum;
}
long long dp[1111][1 << 14];
bool calced[1111][1 << 14];
int qmarks = 0;
int pos[15];
string s;
long long pre_calc[1111][16];
long long uj_all[1111][16];
bool pre_calced[1111][16];
int pre_mask[1 << 14];
int van = 0;
long long calc(int st, int mask) {
  if (calced[st][mask]) return dp[st][mask];
  int ith = pre_mask[mask];
  if (ith == qmarks) {
    if (pre_calced[st][ith]) return pre_calc[st][ith];
    long long res = 0;
    int bef = st;
    for (int i = pos[ith]; i < (int)(s).size(); ++i) {
      if (s[i] != '?') {
        st = get_go(st, s[i]);
        res += tr[st].sum;
      }
    }
    pre_calc[bef][ith] = res;
    pre_calced[bef][ith] = 1;
    calced[bef][mask] = 1;
    return dp[bef][mask] = res;
  }
  int bef = st;
  long long pre = 0;
  if (!pre_calced[st][ith]) {
    int elotte = st;
    for (int i = pos[ith]; i < pos[ith + 1]; i++) {
      if (s[i] != '?') {
        st = get_go(st, s[i]);
        pre += tr[st].sum;
      }
    }
    pre_calc[elotte][ith] = pre;
    pre_calced[elotte][ith] = 1;
    uj_all[elotte][ith] = st;
  } else {
    pre = pre_calc[st][ith];
    st = uj_all[st][ith];
  }
  long long ans = -1LL << 60;
  for (int j = 0; j < 14; ++j) {
    if (((1 << j) & mask) == 0) {
      int kovi = get_go(st, j + 'a');
      ans = max(ans, calc(kovi, mask | (1 << j)) + pre + tr[kovi].sum);
    }
  }
  calced[bef][mask] = 1;
  return dp[bef][mask] = ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int i = 0; i < (1 << 14); ++i) pre_mask[i] = __builtin_popcount(i);
  int k;
  cin >> k;
  for (int i = 0; i < k; ++i) {
    string t;
    cin >> t;
    int cost;
    cin >> cost;
    add_str(t, cost);
  }
  for (int i = 0; i < ind; ++i) fix(i);
  cin >> s;
  int idx = 0;
  for (auto i : s) {
    qmarks += i == '?';
    if (i == '?') {
      pos[qmarks] = idx;
    }
    idx++;
  }
  if (qmarks == 0) {
    int akt = 0;
    long long ans = 0;
    for (auto i : s) {
      akt = get_go(akt, i);
      ans += tr[akt].sum;
    }
    cout << ans << "\n";
  } else {
    cout << calc(0, 0) << "\n";
  }
  return 0;
}

```