CF717G 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` 同时计算。

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