CF717G.Underfail

You have recently fallen through a hole and, after several hours of unconsciousness, have realized you are in an underground city. On one of your regular, daily walks through the unknown, you have encountered two unusually looking skeletons called Sanz and P’pairus, who decided to accompany you and give you some puzzles for seemingly unknown reasons.

One day, Sanz has created a crossword for you. Not any kind of crossword, but a 1D crossword! You are given m words and a string of length n. You are also given an array p, which designates how much each word is worth — the i-th word is worth p__i points. Whenever you find one of the m words in the string, you are given the corresponding number of points. Each position in the crossword can be used at most x times. A certain word can be counted at different places, but you cannot count the same appearance of a word multiple times. If a word is a substring of another word, you can count them both (presuming you haven’t used the positions more than x times).

In order to solve the puzzle, you need to tell Sanz what’s the maximum achievable number of points in the crossword. There is no need to cover all postions, just get the maximal score! Crossword and words contain only lowercase English letters.

你最近不慎掉进一个洞中，经过数小时的昏迷后，发现自己身处一座地下城市。在你每日例行的、漫无目的的探索途中，遇到了两具外形奇特的骷髅——桑兹（Sanz）和佩尔厄斯（P’pairus）。他们决定陪伴你，并出于某种不明原因，给你出了一些谜题。

某一天，桑兹为你设计了一个填字游戏。但这并非普通填字游戏，而是一个一维填字游戏！你将获得 $m$ 个单词、一个长度为 $n$ 的字符串，以及一个数组 $p$，其中 $p_i$ 表示第 $i$ 个单词的分值。每当你在该字符串中找到这 $m$ 个单词中的任意一个时，你即可获得其对应的分数。填字游戏中的每个位置最多可被使用 $x$ 次。同一个单词可在不同位置多次计分，但同一处单词出现不可重复计分。若某单词是另一单词的子串，则二者均可计分（前提是所涉位置未被使用超过 $x$ 次）。

为解开此谜题，你需要告诉桑兹：该一维填字游戏中最高可得分数是多少？无需覆盖字符串中所有位置，只需取得最大可能得分即可！填字字符串及所有单词均由小写英文字母组成。

The first line of the input contains a single integer n (1 ≤ n ≤ 500) — the length of the crossword. The second line contains the crossword string. The third line contains a single integer m (1 ≤ m ≤ 100) — the number of given words, and next m lines contain description of words: each line will have a string representing a non-empty word (its length doesn't exceed the length of the crossword) and integer p__i (0 ≤ p__i ≤ 100). Last line of the input will contain x (1 ≤ x ≤ 100) — maximum number of times a position in crossword can be used.

输入的第一行包含一个整数 $n$（$1 ≤ n ≤ 500$）——填字游戏的长度。
第二行包含填字游戏字符串。
第三行包含一个整数 $m$（$1 ≤ m ≤ 100$）——给定单词的数量；接下来的 $m$ 行描述这些单词：每行包含一个非空字符串（其长度不超过填字游戏的长度）以及一个整数 $p_i$（$0 ≤ p_i ≤ 100$）。
输入的最后一行包含整数 $x$（$1 ≤ x ≤ 100$）——填字游戏中每个位置最多可被使用的次数。

Output single integer — maximum number of points you can get.

输出单个整数——你能获得的最大点数。

For example, with the string "abacba", words "aba" (6 points) and "ba" (3 points), and x = 3, you can get at most 12 points - the word "aba" appears once ("abacba"), while "ba" appears two times ("abacba"). Note that for x = 1, you could get at most 9 points, since you wouldn’t be able to count both "aba" and the first appearance of "ba".

例如，对于字符串 "abacba"、单词 "aba"（6 分）和 "ba"（3 分），以及 x = 3，你最多可获得 12 分——单词 "aba" 出现一次（"abacba"），而 "ba" 出现两次（"abacba"）。注意，当 x = 1 时，你最多只能获得 9 分，因为你无法同时计入 "aba" 和 "ba" 的第一次出现。