Underfail

### **题目描述** 你最近掉进了一个洞里，在昏迷了几个小时后，意识到自己身处一个地下城市。在你每天的漫无目的地游逛中，你遇到了两个长相不寻常的骷髅，他们名叫 Sanz 和 P'pairus 。他们决定陪伴你并给你一些谜题，但你并不知道原因。 有一天，Sanz 为你创建了一个纵向填字游戏。这不是普通的填字游戏，而是一个一维的填字游戏！你会得到 $m$ 个单词和一个长度为 $n$ 的字符串。你还会得到一个数组 $p$，它表示每个单词的价值——第 $i$ 个单词的价值为 $p_i$。每当你在字符串中找到这 $m$ 个单词中的一个 $m_i$，你就会得到相应数量的分数 $p_i$。填字游戏中的每个位置最多只能使用 $x$ 次。同一单词可以在不同的位置被计算，但你不能多次计算同一个单词的出现次数。如果一个单词是另一个单词的子串，那么它们就都可以被计算（假设你没有超过 $x$ 次使用该位置）。 为了解决这个谜题，你需要告诉 Sanz 在这个填字游戏中最大可获得的分数是多少。没有必要覆盖所有位置，只需获得最大分数！填字游戏和单词只包含小写英文字母。 ### **简明题意** 给定一个字符串 $s$ 和 $m$ 个单词，请通过搭配单词使得分最大化。注意：每个位置的字母最多只能被用在 $x$ 个可重复的单词中。 ### **输入格式** 输入的第一行包含一个整数 $n$ $( 1 \le n \le 500 )$。第二行包含一个字符串表示填字游戏。第三行包含一个整数 $m$ $( 1 \le m \le 100 )$，表示给定单词的数量，接下来的 $m$ 行是对单词的描述：每行都有一个表示非空单词的字符串（其长度不超过填字游戏的长度）和一个整数 $p_{i}$ $( 0 \le p_{i} \le 100 )$。输入的最后一行包含一个整数 $x$ $( 1 \le x \le 100 )$，表示填字游戏中一个位置可以使用的最大次数。 ### **输出格式** 输出一个整数，代表你能获得的最大分数。 ### **说明/提示** 对于样例中的字符串 `abacba`，有价值为 $6$ 的单词 `aba` 和价值为 $3$ 的单词 `ba`，最大使用次数为 $3$。你最多能得到 $12$ 分，方式如下：`aba` 一次，`ba` 两次。如果 $x$ 变为了 $1$，你最多只能得到 $9$ 分，因为 `ba` 的第一次出现不能和 `aba` 同时计算。

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.

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.

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

6
abacba
2
aba 6
ba 3
3

12

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".