求卡常/卡空间

# include <bits/stdc++.h>
# include <bits/extc++.h>
# define rep(i, a, b) for(int i = (a);i <= (b);i ++)
# define urep(i, a, b) for(unsigned int i = (a);i <= (b);i ++)
# define lop(i, a, b) for(int i = (a);i <  (b);i ++)
# define dwn(i, a, b) for(int i = (a);i >= (b);i --)
# define int64 long long
# define ___main signed main()
# define f64 double
# define f32 float
# define f128 long double
# define int128 __int128
# define i128 ((__int128)1)
# define ret return
# define inl inline
# define reg register
# define fn void
# define elif else if
# define pb push_back
# define pp pop_back
using std::cout;
using std::cin;
# define CASES() int T;cin >> T;while(T--)
# define FaILurEg(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
# define N 300005
# define mod  100000000000000009
# define modd 100000000000000007
# define B 1024
# define uint unsigned int
int n, m, L, c[N];
std::string M, s[N];
inline int min(int a, int b){return a>b?b:a;}
inline int max(int a, int b){return a<b?b:a;}
constexpr int __B[] = {8, 16, 32, 64, 96,128,256,512,768,1024,1280,1536,1792,2048,2304,2560,2816,3072,3328,3584,3840,4096,4352,4608,4864,5120,5376,5632,5888,6144,6400,6656,6912,7168,7424,7680,7936,8192,8448,8704,8960,9216,9472,9728,9984,10240,10496,10752,11008,11264,11520,11776,12032,12288,12544,12800,13056,13312,13568,13824,14080,14336,14592,14848};
template<typename X>
struct wekter {
   size_t siz;X *mem;signed x = -1;
   inline void push_back(X a) {
      if(mem == nullptr) 
         mem = (X*)std::malloc((sizeof(X)) * __B[++ x]);
      if(siz == __B[x]) 
         mem = (X*)std::realloc(mem,sizeof(X) *__B[++ x]);
      mem[siz ++] = a;
   }
   inline size_t size(){return siz;}
   inline X* begin(){return mem;}
   inline X* end(){return mem + siz;}
};
struct custom_hash {
    inline static int64_t splitmix64(int64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    inline size_t operator()(int64_t x) const {
        static const int64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

namespace smallStr {// for all pref/suf use hashmap
   std::vector<int> Str;
   __gnu_pbds::gp_hash_table<int64, int, custom_hash> G;
   //int G[19373934], GG[19491002];
   void Build() {
      for(auto i : Str) {int64 H0 = 0, H1 = 0;
         //std::cerr << "STRING " << i << " ";
         rep(j, 0, s[i].size() - 1)
            H0 = H0 * 13 + s[i][j] - '/',H0 %= mod,
            G[H0] = ((!G[H0])?c[i]:min(c[i],G[H0]));
         H0 = 0;int64 P = 1, PP = 1;H1 = 0;
         dwn(j, s[i].size() - 1, 0) 
            H0 = H0 + (s[i][j] - '/') * P,H0 %= mod,
            G[H0] = ((!G[H0])?c[i]:min(c[i],G[H0])), 
            P = P * 13 % mod;
         //assert(G.size() <= 600000);
      }
   }
}
namespace bigStr {
   std::vector<int> Str;
   wekter<std::pair<int, int> > Add[N], Qry[N];
   int Z[N * 2];
   void countZ_pref() {
      // assert(Str.size() <= 0);
      std::string S$;
      for(auto I : Str) {
         S$ = s[I] + '$' + M;
         Z[0] = 0;
         int l = 0, r = 0;
         rep(i, 1, S$.size() - 1) {
            if(i <= r && Z[i - l] < r - i + 1) Z[i] = Z[i - l];
            else {
               Z[i] = max(0, r - i + 1);
               while(i + Z[i] < S$.size() && S$[Z[i]] == S$[i + Z[i]]) 
                  Z[i] ++;
               if(i + Z[i] - 1 > r) l = i, r = i + Z[i] - 1;
            }
            if(i > s[I].size() && (Z[i]))
               Add[i - s[I].size()].push_back({I, i - s[I].size() + Z[i] - 1}); 
         }
      }
   }
   void countZ_suf() {
      std::string S$;
      for(auto I : Str) {
         S$ = M + '$' + s[I];
         std::reverse(S$.begin(), S$.end());
         Z[0] = 0;
         int l = 0, r = 0;
         rep(i, 1, S$.size() - 1) {
            if(i <= r && Z[i - l] < r - i + 1) Z[i] = Z[i - l];
            else {
               Z[i] = max(0, r - i + 1);
               while(i + Z[i] < S$.size() && S$[Z[i]] == S$[i + Z[i]]) 
                  Z[i] ++;
               if(i + Z[i] - 1 > r) l = i, r = i + Z[i] - 1;
            }
            if(i > s[I].size() && (Z[i]))
               Qry[m - (i - s[I].size()) + 1].push_back({I, m - (i - s[I].size()) + 1 - Z[i] + 1});
         }
      }
   }
}
int64 dp[N], st[N][20];
int64 Heap[N + 600], Hp[N];
___main {
//FaILurEg("P14212");
   std::ios::sync_with_stdio(0);cin.tie(0);
   cin >> m >> n >> L;cin >> M;
   rep(i, 1, n) cin >> c[i] >> s[i];
   urep(i, 1, B * (m /B + 1)) Heap[i] = 0x3f3f3f3f3f3f3f3f, Hp[i / B] = 0x3f3f3f3f3f3f3f3f;
   rep(i, 1, n) if(s[i].size() < B) smallStr::Str.push_back(i);
                else bigStr::Str.push_back(i);
   smallStr::Build();
   bigStr::countZ_pref();bigStr::countZ_suf();
   rep(i, 1, m) {
      dp[i] = 0x3f3f3f3f3f3f3f3f;
      // if(dp[i] <= 300000000)
      //    std::cerr << i << "xxx\n";
      // smalls
      int64 H = 0, P = 1, HH = 0, PP = 1;
      dwn(j, i - 1, max(0, i - B))
         H = H + (M[j] - '/') * P, H %= mod, P *= 13, P %= mod,
         (smallStr::G.find(H)!=smallStr::G.end())?dp[i] = std::min(dp[j] + smallStr::G[H], dp[i]):91;
      
      //if(dp[i] <= 300000000)
         //std::cerr << dp[i] << "xx\n";
         //std::cout << dp[i] << " \n";
      for(auto [I, R] : bigStr::Add[i])
         Heap[R] = std::min(Heap[R], dp[i - 1] + c[I]),
         Hp[R / B] = std::min(Hp[R / B], Heap[R]);
      int64 Q = 0x3f3f3f3f3f3f3f3f;
      dwn(j, m / B, i / B + 1)
         Q = std::min(Q, Hp[j]);
      dwn(j, (i / B + 1) * B - 1, i)
         Q = std::min(Q, Heap[j]);
      dp[i] = std::min(Q, dp[i]); 
      for(auto [I, L] : bigStr::Qry[i]) {
         // min [L,i]
         //assert(L >= 1);
         int len = i - L + 1, j = std::__lg(len);
         //assert(L - 1 + (1 << j) - 1 >= 0);
         //assert(L + (1 << j) >= 2);
         //assert(L - 1 + (1 << j) - 1 < i);
         int64 T = std::min(st[i - 1][j], st[L - 1 + (1 << j) - 1][j]);
         dp[i] = std::min(dp[i], T + c[I]);
      } 
      // if(dp[i] <= 300000000)
      //    std::cerr << i << "!\n";
      st[i][0] = dp[i];
      for(int j = 1;i - (1 << j) + 1 >= 0;j ++)
         st[i][j] = std::min(st[i][j - 1], st[i - (1 << (j- 1))][j - 1]);
      // if(dp[i] <= 300000000)
      //    std::cerr << i << "?\n";
   }
   cout << (dp[m]<0x3f3f3f3f3f3f3f3f?dp[m]:-1) << "\n";
   ret 0;}