min cost max flow

///#include <stdio.h>
///#include <iostream>
///#include <cstring>
///#include <cmath>
///#include <algorithm>
///#include <string>
///#include <vector>
///#include <map>
///#include <set>
///#include <queue>
///#include <cstdlib>
///#include <limits>
///#include <iostream>
///#include <sstream>
///#include <unordered_set>
///#include <unordered_map>
///#include <random>
#include <bits/stdc++.h>
///#include <bits/stdtr1c++.h>
///#include <ext/pb_ds/assoc_container.hpp>
///#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
///using namespace __gnu_pbds;
#define              MAX             100005
#define              EPS             1e-9
#define              ull             unsigned long long
#define              ll              long long
#define              inf             INT_MAX
#define              pi              acos(-1.0)
#define              vi              vector<int>
#define              vl              vector<long long>
#define              pii             pair<int,int>
#define              pll             pair<long long,long long>
#define              mp              make_pair
#define              mem(a, v)       memset(a, v, sizeof (a))
#define              mod             1000000007
#define              all(a)          a.begin(),a.end()
#define              rall(a)         a.rbegin(),a.rend()
#define              ff              first
#define              ss              second
#define              arsort(ar,n)    sort(ar,ar+n);
#define              vsort(v)        sort(v.begin(),v.end())
#define              vrev(v)         reverse(v.begin(),v.end())
#define              arrev(ar,n)     reverse(ar,ar+n)
#define              pb              push_back
#define              popb            pop_back
#define              booster()       ios_base::sync_with_stdio(0); cin.tie(0);
#define              read(f)         freopen(f, "r", stdin)
#define              scani(x)        scanf("%d",&x)
#define              scanl(x)        scanf("%I64d",&x)
#define              scand(x)        scanf("%lf",&x)
#define              scans(x)        scanf("%s",x)
#define              min3(a,b,c)     min(a,min(b,c))
#define              max3(a,b,c)     max(a,max(b,c))
#define              min4(a,b,c,d)   min(min(a,b),min(c,d))
#define              max4(a,b,c,d)   max(max(a,b),max(c,d))
#define              max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define              min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))

#define              bitCheck(a,k)     ((bool)(a&(1<<(k))))
#define              bitOff(a,k)       (a&(~(1<<(k))))
#define              bitOn(a,k)        (a|(1<<(k)))
#define              bitFlip(a,k)      (a^(1<<(k)))

#define              POPCOUNT           __builtin_popcount
#define              POPCOUNTLL         __builtin_popcountll
#define              RIGHTMOST          __builtin_ctzll
#define              LEFTMOST(x)        (63-__builtin_clzll((x)))

#define scani2(a,b) scani(a) , scani(b)
#define scani3(a,b,c) scani(a), scani(b), scani(c)
#define scani4(a,b,c,d) scani(a), scani(b), scani(c), scani(d)
#define scani5(a,b,c,d,e) scani(a), scani(b), scani(c), scani(d) , scani(e)



/*********************Ordered Multiset*************************/


/*** Needs C++11 or C++14 ***/
/// Treap supporting duplicating values in set
/// Maximum value of treap * ADD must fit in long long

/**

struct Treap{ /// hash = 96814
    int len;
    const int ADD = 1000010;
    const int MAXVAL = 1000000010;
    tr1::unordered_map <long long, int> mp; /// Change to int if only int in treap
    tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> T;
    Treap(){
        len = 0;
        T.clear(), mp.clear();
    }
    inline void clear(){
        len = 0;
        T.clear(), mp.clear();
    }
    inline void insert(long long x){
        len++, x += MAXVAL;
        int c = mp[x]++;
        T.insert((x * ADD) + c);
    }
    inline void erase(long long x){
        x += MAXVAL;
        int c = mp[x];
        if (c){
            c--, mp[x]--, len--;
            T.erase((x * ADD) + c);
        }
    }
    /// 1-based index, returns the K'th element in the treap, -1 if none exists
    inline long long kth(int k){
        if (k < 1 || k > len) return -1;
        auto it = T.find_by_order(--k);
        return ((*it) / ADD) - MAXVAL;
    }
    /// Count of value < x in treap
    inline int count(long long x){
        x += MAXVAL;
        int c = mp[--x];
        return (T.order_of_key((x * ADD) + c));
    }
    /// Number of elements in treap
    inline int size(){
        return len;
    }
};



typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;///*X.find_by_order();X.order_of_key();**/
template <class T> inline bool isLeap(T y) {return (y % 400 == 0) || (y % 100 ? y % 4 == 0 : false); }
template< class T > inline T gcd(T a, T b) { return (b) == 0 ? (a) : gcd((b), ((a) % (b))); }
template< class T > inline T lcm(T a, T b) { return ((a) / gcd((a), (b)) * (b)); }
template <class T> inline T BigMod(T Base,T power,T M=mod){if(power==0)return 1;if(power&1)return ((Base%M)*(BigMod(Base,power-1,M)%M))%M;else{T y=BigMod(Base,power/2,M)%M;return (y*y)%M;}}
template <class T> inline T ModInv (T A,T M = mod){return BigMod(A,M-2,M);}

int fx[] = {-1,+0,+1,+0,+1,+1,-1,-1,+0};
int fy[] = {+0,-1,+0,+1,+1,-1,+1,-1,+0};
int day[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};


/*********************** let the play begin() ***********************************/


int pt[MAX];vi v[MAX];string ptt[MAX];int ans,dtt[MAX],non[505][505],fl[505],pos1[505],pos2[505],cl[505];

const int N = 505*2;
const ll INF=(ll)1<<60;
struct Edge{
    ll from,to,cap,flow,cost;
    Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost) {}
};
namespace mcmf{
    int n,m,s,t;
    vector<Edge> edges;
    vector<ll> G[N];
    bool inq[N];
    ll d[N],p[N],a[N];                     /// N = Size of nodes in flow network
    void init(int src,int sink,int node)
    {
        n=node;
        s= src;
        t = sink;
        edges.clear();
        for(int i=0;i<=n;++i) G[i].clear();
    }
    void addEdge(int from,int to,ll cap,ll cost)
    {
        edges.push_back(Edge(from,to,cap,0,cost));
        edges.push_back(Edge(to,from,0,0,-cost));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    bool spfa(ll &flow,ll& cost)
    {
        for(int i=0;i<=n;++i) d[i]=INF,inq[i]=0;
        queue<int> que;
        que.push(s);
        inq[s]=1;d[s]=0;p[s]=0;a[s]=INF;
        while(!que.empty())
        {
            int x=que.front();que.pop();
            inq[x]=0;
            for(int i=0;i<G[x].size();++i)
            {
                Edge &e=edges[G[x][i]];
                if(e.cap>e.flow && d[e.to]>d[x]+e.cost)
                {
                    d[e.to]=d[x]+e.cost;
                    p[e.to]=G[x][i];
                    a[e.to]=min(a[x],e.cap-e.flow);
                    if(!inq[e.to]) inq[e.to]=1,que.push(e.to);
                }
            }
        }
        if(d[t]==INF) return 0;
        flow+=a[t];
        cost+=d[t];    /// multiply by d[t]*a[t] if per unit cost is given.
        int u=t;
        while(u!=s)
        {
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
            u=edges[p[u]].from;
        }
        return 1;
    }
    pll solve()
    {
        ll flow=0,cost=0;
        while(spfa(flow,cost));
        return make_pair(cost,flow);
    }
}

int sor;

int occ(string s,string ss,int indx)
{
    int z[1005];
    mem(z,0);

    int n = s.length();

    int L = 0, R = 0;
for (int i = 1; i < n; i++) {
  if (i > R) {
    L = R = i;
    while (R < n && s[R-L] == s[R]) R++;
    z[i] = R-L; R--;
  } else {
    int k = i-L;
    if (z[k] < R-i+1) z[i] = z[k];
    else {
      L = i;
      while (R < n && s[R-L] == s[R]) R++;
      z[i] = R-L; R--;
    }
  }
}
    int cnt = 0;
    for(int i = 0;i<n;i++)
    {
        if(z[i]==ss.length())
        {
            mcmf::addEdge(i-ss.length()-1,i-1,1,-dtt[indx]);

        }
    }
    return cnt;

}



int main()
{
    booster()
    ///read("input.txt");

    string s;
    int n;
    cin>>n>>s;
    int cnt = 0;
    for(int i = 0;i<n;i++)
    {
        pos1[i] = cnt++;
        pos2[i] = cnt++;
    }
    ///cout<<cnt<<endl;
    sor = cnt;
    mcmf::init(n+1,n+2,n+3);
    int m;
    cin>>m;
    for(int i = 0;i<m;i++)
    {
        cin>>ptt[i]>>dtt[i];
    }
    int q;
    cin>>q;
    for(int i = 0;i<n;i++)mcmf::addEdge(i,i+1,q,0);
    for(int i = 0;i<m;i++)
    {
        string ss = ptt[i]+'#'+s;
        occ(ss,ptt[i],i);
    }
    mcmf::addEdge(n+1,0,q,0);
    mcmf::addEdge(n,n+2,q,0);
    pll x = mcmf::solve();
    cout<<-x.ff;




    return 0;
}