#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
template <typename T>
void read(T& x) {
  x = 0;
  char ch = getchar();
  long long f = 1;
  while (!isdigit(ch)) {
    if (ch == '-') f *= -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  x *= f;
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
const int N = 1010;
struct AC_Auto {
  int sz = 0;
  int tri[N][14], end[N], fail[N];
  int tri2[N][14];
  int nxt[400010];
  int loc[N];
  long long add[N];
  unordered_map<int, long long, custom_hash> f;
  int init(int id = 0) {
    memset(tri[id], 0, sizeof(tri[id]));
    memset(tri2[id], 0, sizeof(tri[id]));
    end[id] = fail[id] = 0;
    return sz = id;
  }
  int insert(const char* s, int cost) {
    int x = 0;
    for (int i = 0; s[i]; ++i) {
      int& v = tri[x][s[i] - 'a'];
      if (v == 0) v = init(sz + 1);
      x = v;
    }
    end[x] += cost;
    return x;
  }
  void build() {
    memcpy(tri2, tri, sizeof(tri));
    queue<int> q;
    for (auto v : tri[0]) {
      if (v) {
        fail[v] = 0;
        q.push(v);
      }
    }
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (int i = 0; i < 14; ++i) {
        int& v = tri[x][i];
        if (v) {
          fail[v] = tri[fail[x]][i];
          end[v] += end[fail[v]];
          q.push(v);
        } else {
          v = tri[fail[x]][i];
        }
      }
    }
  }
  void fuck(const char* s) {
    const int m = (1 << 14) - 1;
    int n = 0;
    int pre = -1;
    memset(nxt, -1, sizeof(nxt));
    for (int i = 0; s[i]; ++i, ++n) {
      if (s[i] == '?') {
        if (pre != i - 1) nxt[pre + 1] = i - 1;
        pre = i;
      }
    }
    nxt[pre + 1] = n - 1;
    f[0] = 0;
    int now = 0;
    while (now < n) {
      if (nxt[now] != -1) {
        int r = nxt[now];
        assert(r < n);
        unordered_set<int, custom_hash> dif;
        unordered_map<int, long long, custom_hash> g;
        for (auto [fk, tmp] : f) {
          int j = fk >> 14;
          assert(j <= sz);
          dif.insert(j);
          add[j] = 0;
          loc[j] = j;
        }
        while (now <= r) {
          int c = s[now++] - 'a';
          assert(c >= 0 && c < 14);
          for (auto v : dif) {
            loc[v] = tri[loc[v]][c];
            add[v] += end[loc[v]];
          }
        }
        for (auto [fk, tmp] : f) {
          int j = fk >> 14;
          assert(j <= sz);
          int k = fk & m;
          int nst = loc[j] << 14;
          nst |= k;
          if (g.find(nst) == g.end())
            g[nst] = tmp + add[j];
          else
            g[nst] = max(g[nst], tmp + add[j]);
        }
        swap(f, g);
      } else {
        assert(s[now] == '?');
        unordered_map<int, long long, custom_hash> g;
        for (auto [fk, tmp] : f) {
          int j = fk >> 14;
          assert(j <= sz);
          int k = fk & m;
          for (int p = 0, msk = 1; p < 14; ++p, msk <<= 1) {
            if (k & msk) continue;
            int x = tri[j][p];
            int nst = x << 14;
            nst |= (k | msk);
            if (g.find(nst) == g.end())
              g[nst] = tmp + end[x];
            else
              g[nst] = max(g[nst], tmp + end[x]);
          }
        }
        swap(f, g);
        ++now;
      }
    }
    long long ans = -0x3f3f3f3f3f3f3f3f;
    for (auto [v, tmp] : f) ans = max(ans, tmp);
    cout << ans;
  }
} AC;
string s;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  int x;
  cin >> n;
  while (n--) {
    cin >> s >> x;
    AC.insert(s.c_str(), x);
  }
  AC.build();
  cin >> s;
  AC.fuck(s.c_str());
  return 0;
}

### Prompt

Please formulate 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>
#pragma GCC optimize("Ofast")
using namespace std;
template <typename T>
void read(T& x) {
  x = 0;
  char ch = getchar();
  long long f = 1;
  while (!isdigit(ch)) {
    if (ch == '-') f *= -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  x *= f;
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
const int N = 1010;
struct AC_Auto {
  int sz = 0;
  int tri[N][14], end[N], fail[N];
  int tri2[N][14];
  int nxt[400010];
  int loc[N];
  long long add[N];
  unordered_map<int, long long, custom_hash> f;
  int init(int id = 0) {
    memset(tri[id], 0, sizeof(tri[id]));
    memset(tri2[id], 0, sizeof(tri[id]));
    end[id] = fail[id] = 0;
    return sz = id;
  }
  int insert(const char* s, int cost) {
    int x = 0;
    for (int i = 0; s[i]; ++i) {
      int& v = tri[x][s[i] - 'a'];
      if (v == 0) v = init(sz + 1);
      x = v;
    }
    end[x] += cost;
    return x;
  }
  void build() {
    memcpy(tri2, tri, sizeof(tri));
    queue<int> q;
    for (auto v : tri[0]) {
      if (v) {
        fail[v] = 0;
        q.push(v);
      }
    }
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (int i = 0; i < 14; ++i) {
        int& v = tri[x][i];
        if (v) {
          fail[v] = tri[fail[x]][i];
          end[v] += end[fail[v]];
          q.push(v);
        } else {
          v = tri[fail[x]][i];
        }
      }
    }
  }
  void fuck(const char* s) {
    const int m = (1 << 14) - 1;
    int n = 0;
    int pre = -1;
    memset(nxt, -1, sizeof(nxt));
    for (int i = 0; s[i]; ++i, ++n) {
      if (s[i] == '?') {
        if (pre != i - 1) nxt[pre + 1] = i - 1;
        pre = i;
      }
    }
    nxt[pre + 1] = n - 1;
    f[0] = 0;
    int now = 0;
    while (now < n) {
      if (nxt[now] != -1) {
        int r = nxt[now];
        assert(r < n);
        unordered_set<int, custom_hash> dif;
        unordered_map<int, long long, custom_hash> g;
        for (auto [fk, tmp] : f) {
          int j = fk >> 14;
          assert(j <= sz);
          dif.insert(j);
          add[j] = 0;
          loc[j] = j;
        }
        while (now <= r) {
          int c = s[now++] - 'a';
          assert(c >= 0 && c < 14);
          for (auto v : dif) {
            loc[v] = tri[loc[v]][c];
            add[v] += end[loc[v]];
          }
        }
        for (auto [fk, tmp] : f) {
          int j = fk >> 14;
          assert(j <= sz);
          int k = fk & m;
          int nst = loc[j] << 14;
          nst |= k;
          if (g.find(nst) == g.end())
            g[nst] = tmp + add[j];
          else
            g[nst] = max(g[nst], tmp + add[j]);
        }
        swap(f, g);
      } else {
        assert(s[now] == '?');
        unordered_map<int, long long, custom_hash> g;
        for (auto [fk, tmp] : f) {
          int j = fk >> 14;
          assert(j <= sz);
          int k = fk & m;
          for (int p = 0, msk = 1; p < 14; ++p, msk <<= 1) {
            if (k & msk) continue;
            int x = tri[j][p];
            int nst = x << 14;
            nst |= (k | msk);
            if (g.find(nst) == g.end())
              g[nst] = tmp + end[x];
            else
              g[nst] = max(g[nst], tmp + end[x]);
          }
        }
        swap(f, g);
        ++now;
      }
    }
    long long ans = -0x3f3f3f3f3f3f3f3f;
    for (auto [v, tmp] : f) ans = max(ans, tmp);
    cout << ans;
  }
} AC;
string s;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  int x;
  cin >> n;
  while (n--) {
    cin >> s >> x;
    AC.insert(s.c_str(), x);
  }
  AC.build();
  cin >> s;
  AC.fuck(s.c_str());
  return 0;
}

```