TLE 95 B

//misaka and rin will carry me to cm
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <array>
#include <tuple>
#include <map>
#include <unordered_map>

#define ll long long
#define lb long double
#define sz(vec) ((int)(vec.size()))
#define all(x) x.begin(), x.end()

const lb eps = 1e-9;
const ll mod = 1e9 + 7, ll_max = 1e18;
//const ll mod = (1 << (23)) * 119 +1;
const int MX = 5e5 +10, int_max = 0x3f3f3f3f;

using namespace std;

typedef uint64_t ull;
static int C = 1009; // initialized below

// Arithmetic mod two primes and 2^32 simultaneously.
// "typedef uint64_t H;" instead if Thue-Morse does not apply.
template<int M, class B>
struct A {
    int x; B b; A(int x=0) : x(x), b(x) {}
    A(int x, B b) : x(x), b(b) {}
    A operator+(A o){int y = x+o.x; return{y - (y>=M)*M, b+o.b};}
    A operator-(A o){int y = x-o.x; return{y + (y< 0)*M, b-o.b};}
    A operator*(A o) { return {(int)(1LL*x*o.x % M), b*o.b}; }
    explicit operator ull() { return x ^ (ull) b << 21; }
    bool operator==(A o){ return ull(*this) == ull(o); }
    bool operator!=(A o){ return ull(*this) != ull(o); }
};
//typedef A<1000000007, A<1000000009, unsigned>> H;
typedef uint64_t H;
struct HashInterval {
    int n;
    vector<H> ha, pw;
    HashInterval(string& str) : ha(sz(str)+1), pw(ha) {
        n = sz(str);
        pw[0] = 1;
        ha[0] = 1;
        for(int i = 0; i< sz(str); i++)
            ha[i+1] = ha[i] * C + str[i],
            pw[i+1] = pw[i] * C;
    }
    H get(int a, int b) { // hash [a, b)
        return ha[b] - ha[a] * pw[b - a];
    }
};

vector<H> getHashes(string& str, int length) {
    if (sz(str) < length) return {};
    H h = 0, pw = 1;
    for(int i = 0; i <length; i++)
        h = h * C + str[i], pw = pw * C;
    vector<H> ret = {h};
    for(int i = length; i<sz(str); i++) {
        ret.push_back(h = h * C + str[i] - pw * str[i-length]);
    }
    return ret;
}

H hashString(string& s){H h{}; for(char c:s) h=h*C+c;return h;}

int lcp(HashInterval& a, HashInterval& b){ //length of lcp of two strings
    if (a.n == 0 || b.n == 0 || a.get(0, 0) != b.get(0, 0)) return 0;
    int lo=0, hi=min(a.n, b.n)+1, mid=(lo+hi)/2;
    while (lo < mid && mid < hi){
        if (a.get(0, mid-1) == b.get(0, mid-1)) lo=mid;
        else hi=mid;
        mid=(lo+hi)/2;
    }
    return lo;
}

unordered_map<ull, ll> adj[MX];
//set<HashInterval> adj[MX];
string str;
unordered_map<ull, ll> price;
ll dp[MX];
int m, cnt[MX];
vector<pair<int, ull>> yes;
vector<int> useful;
void solve(){
    cin >> m;
    price.reserve(m);
    for(int i = 0; i<m; i++){
        string a; int b;
        cin >> a >> b;
        H temp = hashString(a);
        ull ttt = (ull)(temp);
        if(price.count(ttt)) price[ttt] = min((ll)b, price[ttt]);
        else price[ttt] = (ll)b;
        cnt[sz(a)]++;
        yes.push_back(make_pair(sz(a), ttt));
        //adj[sz(a)]
    }
    cin >> str;
    for(int i = 1; i<=sz(str); i++){
        if(cnt[i]) useful.push_back(i);
    }
    HashInterval ash = HashInterval(str);
    memset(dp, 63, sizeof(dp));
    dp[0] = 0;
    for(int i = 1; i<=sz(str); i++){
        for(int j : useful){
            if(j > i) break;
            ull t = (ull)(ash.get(i-j, i));
            if(dp[i - j] <= (1e18) && price.count(t)) dp[i] = min(dp[i], dp[i-j] + price[t]);
        }
    }
    cout << ((dp[sz(str)] > 1e18) ? (-1) : (dp[sz(str)])) << "\n";
}

int main(){
  cin.tie(0) -> sync_with_stdio(0);
    int T = 1;
    //cin >> T;
  while(T--){
        solve();
    }
    return 0;
}