G. Underfail

#pragma GCC optimize("Ofast,unroll-loops")
#include <algorithm>
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define fi first
#define se second

#define lsb(x) (x & (-x))

using namespace std;

#define int long long

inline bool ckmin(int &a, int b) { if (a <= b) return false; else a = b; return true; }
inline bool ckmax(int &a, int b) { if (a >= b) return false; else a = b; return true; }

typedef long long ll;
typedef pair<int, int> pii;

const int NMAX = 505;
const int INF = 2e18+5;

struct Edge {
    int dest, cap, cost, other;
};

int n, m, x;
char s[NMAX];
char a[NMAX][NMAX];
int p[NMAX];
int source, sink;
vector<Edge> g[NMAX];
int dist[NMAX], pi[NMAX], pi2[NMAX];
int vis[NMAX];
bool inq[NMAX];
pii nxt[NMAX];

void add_edge(int x, int y, int cap, int cost) {
    if (!cap) return;
    g[x].push_back({ y, cap, cost, sz(g[y]) });
    g[y].push_back({ x, 0, -cost, sz(g[x]) - 1 });
}

void read() {
    cin >> n >> (s + 1) >> m;
    for (int i = 1; i <= m; i++)
        cin >> (a[i] + 1) >> p[i];
    cin >> x;
}

void init_pi() {
    for (int i = 1; i <= n; i++)
        pi[i] = INF;
    pi[source] = 0;

    queue<int32_t> qe;

    qe.push(source);

    while (!qe.empty()) {
        int u = qe.front();

        qe.pop();
        inq[u] = false;

        for (auto &it : g[u]) {
            if (it.cap && ckmin(pi[it.dest], pi[u] + it.cost)) {
                if (!inq[it.dest]) {
                    qe.push(it.dest);
                    inq[it.dest] = true;
                }
            }
        }
    }
}

void dijkstra() {
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        vis[i] = false;
        pi2[i] = pi[i];
    }

    priority_queue<pair<ll, int32_t>> pq;

    pq.push({0, source});
    dist[source] = pi[source] = 0;
    nxt[source] = {0, 0};
    int32_t i = 0;

    while (!pq.empty()) {
        int u = pq.top().se;

        pq.pop();

        if (vis[u]) continue;
        vis[u] = true;

        i = 0;
        for (auto &it : g[u]) {
            if (it.cap && ckmin(dist[it.dest], dist[u] + it.cost + pi2[u] - pi2[it.dest])) {
                pi[it.dest] = pi[u] + it.cost;
                nxt[it.dest] = { u, i };
                pq.push({-dist[it.dest], it.dest});
            }
            i++;
        }
    }
}

int mcf(int max_flow) {
    int min_cost = 0;
    init_pi();
    while (dijkstra(), dist[sink] != INF && max_flow) {
        int flow = max_flow, cost = 0;
        for (int u = sink; u != source; u = nxt[u].fi) {
            Edge &e = g[nxt[u].fi][nxt[u].se];
            cost += e.cost;
            ckmin(flow, e.cap);
        }
        for (int u = sink; u != source; u = nxt[u].fi) {
            Edge &e = g[nxt[u].fi][nxt[u].se];
            e.cap -= flow;
            g[u][e.other].cap += flow;
        }
        max_flow -= flow;
        min_cost += flow * cost;
    }
    return min_cost;
}

int solve() {
    source = n + 1, sink = n + 2;
    add_edge(source, 1, x, 0);
    for (int i = 1; i < n; i++)
        add_edge(i, i + 1, x, 0);
    add_edge(n, sink, x, 0);
    for (int j = 1; j <= m; j++) {
        int l = strlen(a[j] + 1);
        for (int i = 1; i <= n - l + 1; i++) {
            if (strncmp(s + i, a[j] + 1, l) == 0) {
                if (i == n - l + 1) add_edge(i, sink, 1, -p[j]);
                else add_edge(i, i + l, 1, -p[j]);
            }
        }
    }
    n += 2;
    return -mcf(INF);
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    read();
    cout << solve() << endl;
    return 0;
}