#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const int inf = 2000000000;
const long long infLL = 9000000000000000000;
template <typename first, typename second>
ostream& operator<<(ostream& os, const pair<first, second>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ",";
    os << *it;
  }
  return os << "]";
}
template <typename T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}
template <typename first, typename second>
ostream& operator<<(ostream& os, const map<first, second>& v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << it->first << " = " << it->second;
  }
  return os << "]";
}
void faltu() { cerr << '\n'; }
template <typename T>
void faltu(T a[], int n) {
  for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
  cerr << '\n';
}
template <typename T, typename... hello>
void faltu(T arg, const hello&... rest) {
  cerr << arg << ' ';
  faltu(rest...);
}
inline bool checkBit(long long n, int i) { return n & (1LL << i); }
inline long long setBit(long long n, int i) {
  return n | (1LL << i);
  ;
}
inline long long resetBit(long long n, int i) { return n & (~(1LL << i)); }
const int ALPHA = 14;
struct AhoCorasick {
  struct Vertex {
    int edge[ALPHA];
    bool leaf = false;
    int p = -1;
    char pch;
    int link = -1;
    int go[ALPHA];
    int cost;
    int dpcost;
    bool dpcost_vis;
    Vertex(int p = -1, char ch = '$') : p(p), pch(ch) {
      memset(edge, -1, sizeof(edge));
      memset(go, -1, sizeof(go));
      cost = 0, dpcost = 0, dpcost_vis = 0;
    }
  };
  vector<Vertex> trie;
  AhoCorasick() : trie(1) {}
  void add_string(string const& s, int c) {
    int node = 0;
    for (char ch : s) {
      int ch_idx = ch - 'a';
      if (trie[node].edge[ch_idx] == -1) {
        trie[node].edge[ch_idx] = trie.size();
        trie.push_back(Vertex(node, ch));
      }
      node = trie[node].edge[ch_idx];
    }
    trie[node].leaf = true;
    trie[node].cost += c;
  }
  int get_link(int node) {
    if (trie[node].link == -1) {
      if (node == 0 || trie[node].p == 0)
        trie[node].link = 0;
      else
        trie[node].link = go(get_link(trie[node].p), trie[node].pch);
    }
    return trie[node].link;
  }
  int go(int node, char ch) {
    int ch_idx = ch - 'a';
    if (trie[node].go[ch_idx] == -1) {
      if (trie[node].edge[ch_idx] != -1)
        trie[node].go[ch_idx] = trie[node].edge[ch_idx];
      else
        trie[node].go[ch_idx] = (node == 0) ? 0 : go(get_link(node), ch);
    }
    return trie[node].go[ch_idx];
  }
  int get_dpcost(int node) {
    if (node == 0) return 0;
    if (trie[node].dpcost_vis) return trie[node].dpcost;
    trie[node].dpcost_vis = 1;
    trie[node].dpcost = trie[node].cost + get_dpcost(get_link(node));
    return trie[node].dpcost;
  }
};
int k;
string t[1005];
int c[1005];
string second;
vector<int> vec;
int qcnt;
long long dp1[1 << 14][1005];
pair<long long, long long> dp2[14][1005];
bool dp1_vis[1 << 14][1005];
bool dp2_vis[14][1005];
AhoCorasick aho;
pair<long long, long long> func(int node, int pos, int idx) {
  if (dp2_vis[pos][node]) return dp2[pos][node];
  dp2_vis[pos][node] = 1;
  long long ans = 0;
  int node_fix = node;
  for (int i = idx; i < second.size(); ++i) {
    if (second[i] == '?') break;
    node = aho.go(node, second[i]);
    ans += aho.get_dpcost(node);
  }
  dp2[pos][node_fix] = make_pair(ans, node);
  return make_pair(ans, node);
}
long long recur1(int mask, int node) {
  int pop = __builtin_popcount(mask);
  if (pop == qcnt) return 0;
  if (dp1_vis[mask][node]) return dp1[mask][node];
  dp1_vis[mask][node] = 1;
  long long ret = -infLL;
  for (int i = 0; i < 14; ++i) {
    if (!checkBit(mask, i)) {
      char ch = 'a' + i;
      int temp_node = aho.go(node, ch);
      long long temp_ans = aho.get_dpcost(temp_node);
      pair<long long, long long> p = func(temp_node, pop, vec[pop] + 1);
      temp_ans += p.first;
      int temp_mask = setBit(mask, i);
      ret = max(ret, temp_ans + recur1(setBit(mask, i), p.second));
    }
  }
  dp1[mask][node] = ret;
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> k;
  for (int i = 0; i < k; ++i) {
    cin >> t[i] >> c[i];
    aho.add_string(t[i], c[i]);
  }
  cin >> second;
  for (int i = 0; i < second.size(); ++i) {
    if (second[i] == '?') {
      ++qcnt;
      vec.push_back(i);
    }
  }
  long long ans = 0;
  int node = 0;
  for (int i = 0; i < second.size(); ++i) {
    ans += aho.get_dpcost(node);
    if (second[i] == '?') break;
    node = aho.go(node, second[i]);
  }
  if (qcnt == 0) ans += aho.get_dpcost(node);
  ans += recur1(0, node);
  cout << ans << '\n';
}

### Prompt

Create a solution in Cpp for 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 eps = 1e-9;
const int inf = 2000000000;
const long long infLL = 9000000000000000000;
template <typename first, typename second>
ostream& operator<<(ostream& os, const pair<first, second>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ",";
    os << *it;
  }
  return os << "]";
}
template <typename T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}
template <typename first, typename second>
ostream& operator<<(ostream& os, const map<first, second>& v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << it->first << " = " << it->second;
  }
  return os << "]";
}
void faltu() { cerr << '\n'; }
template <typename T>
void faltu(T a[], int n) {
  for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
  cerr << '\n';
}
template <typename T, typename... hello>
void faltu(T arg, const hello&... rest) {
  cerr << arg << ' ';
  faltu(rest...);
}
inline bool checkBit(long long n, int i) { return n & (1LL << i); }
inline long long setBit(long long n, int i) {
  return n | (1LL << i);
  ;
}
inline long long resetBit(long long n, int i) { return n & (~(1LL << i)); }
const int ALPHA = 14;
struct AhoCorasick {
  struct Vertex {
    int edge[ALPHA];
    bool leaf = false;
    int p = -1;
    char pch;
    int link = -1;
    int go[ALPHA];
    int cost;
    int dpcost;
    bool dpcost_vis;
    Vertex(int p = -1, char ch = '$') : p(p), pch(ch) {
      memset(edge, -1, sizeof(edge));
      memset(go, -1, sizeof(go));
      cost = 0, dpcost = 0, dpcost_vis = 0;
    }
  };
  vector<Vertex> trie;
  AhoCorasick() : trie(1) {}
  void add_string(string const& s, int c) {
    int node = 0;
    for (char ch : s) {
      int ch_idx = ch - 'a';
      if (trie[node].edge[ch_idx] == -1) {
        trie[node].edge[ch_idx] = trie.size();
        trie.push_back(Vertex(node, ch));
      }
      node = trie[node].edge[ch_idx];
    }
    trie[node].leaf = true;
    trie[node].cost += c;
  }
  int get_link(int node) {
    if (trie[node].link == -1) {
      if (node == 0 || trie[node].p == 0)
        trie[node].link = 0;
      else
        trie[node].link = go(get_link(trie[node].p), trie[node].pch);
    }
    return trie[node].link;
  }
  int go(int node, char ch) {
    int ch_idx = ch - 'a';
    if (trie[node].go[ch_idx] == -1) {
      if (trie[node].edge[ch_idx] != -1)
        trie[node].go[ch_idx] = trie[node].edge[ch_idx];
      else
        trie[node].go[ch_idx] = (node == 0) ? 0 : go(get_link(node), ch);
    }
    return trie[node].go[ch_idx];
  }
  int get_dpcost(int node) {
    if (node == 0) return 0;
    if (trie[node].dpcost_vis) return trie[node].dpcost;
    trie[node].dpcost_vis = 1;
    trie[node].dpcost = trie[node].cost + get_dpcost(get_link(node));
    return trie[node].dpcost;
  }
};
int k;
string t[1005];
int c[1005];
string second;
vector<int> vec;
int qcnt;
long long dp1[1 << 14][1005];
pair<long long, long long> dp2[14][1005];
bool dp1_vis[1 << 14][1005];
bool dp2_vis[14][1005];
AhoCorasick aho;
pair<long long, long long> func(int node, int pos, int idx) {
  if (dp2_vis[pos][node]) return dp2[pos][node];
  dp2_vis[pos][node] = 1;
  long long ans = 0;
  int node_fix = node;
  for (int i = idx; i < second.size(); ++i) {
    if (second[i] == '?') break;
    node = aho.go(node, second[i]);
    ans += aho.get_dpcost(node);
  }
  dp2[pos][node_fix] = make_pair(ans, node);
  return make_pair(ans, node);
}
long long recur1(int mask, int node) {
  int pop = __builtin_popcount(mask);
  if (pop == qcnt) return 0;
  if (dp1_vis[mask][node]) return dp1[mask][node];
  dp1_vis[mask][node] = 1;
  long long ret = -infLL;
  for (int i = 0; i < 14; ++i) {
    if (!checkBit(mask, i)) {
      char ch = 'a' + i;
      int temp_node = aho.go(node, ch);
      long long temp_ans = aho.get_dpcost(temp_node);
      pair<long long, long long> p = func(temp_node, pop, vec[pop] + 1);
      temp_ans += p.first;
      int temp_mask = setBit(mask, i);
      ret = max(ret, temp_ans + recur1(setBit(mask, i), p.second));
    }
  }
  dp1[mask][node] = ret;
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> k;
  for (int i = 0; i < k; ++i) {
    cin >> t[i] >> c[i];
    aho.add_string(t[i], c[i]);
  }
  cin >> second;
  for (int i = 0; i < second.size(); ++i) {
    if (second[i] == '?') {
      ++qcnt;
      vec.push_back(i);
    }
  }
  long long ans = 0;
  int node = 0;
  for (int i = 0; i < second.size(); ++i) {
    ans += aho.get_dpcost(node);
    if (second[i] == '?') break;
    node = aho.go(node, second[i]);
  }
  if (qcnt == 0) ans += aho.get_dpcost(node);
  ans += recur1(0, node);
  cout << ans << '\n';
}

```