你最近掉进了一个洞,在昏迷了几个小时后,意识到自己身处地下城。在一次例行的、每日穿越未知世界的散步中,你遇到了两个长相异常的骷髅,名叫桑兹 (Sanz) 和 P’pairus,他们决定陪伴你,并出于看似未知的原因给你一些谜题。
有一天,Sanz 为您创建了一个填字游戏。不是任何类型的填字游戏,而是一维填字游戏!给你 m 个单词和一个长度为 n 的字符串。您还会获得一个数组 p,它指定每个单词的价值 - 第 i 个单词值 pi 点。每当您在字符串中找到 m 个单词之一时,就会获得相应的点数。填字游戏中的每个位置最多可以使用 x 次。某个单词可以在不同的地方进行计数,但不能对同一个单词的多次出现进行计数。如果一个单词是另一个单词的子串,您可以对它们进行计数(假设您使用这些位置的次数不超过 x 次)。
为了解决这个难题,您需要告诉 Sanz 填字游戏中可达到的最大点数是多少。无需涵盖所有位置,只需获得最高分即可!填字游戏和单词仅包含小写英文字母。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 500) — 填字游戏的长度。第二行包含填字游戏字符串。第三行包含一个整数 m (1 ≤ m ≤ 100) — 给定单词的数量,接下来的 m 行包含单词的描述:每行将有一个表示非空单词的字符串(其长度不超过填字游戏的长度)和整数 pi (0 ≤ pi ≤ 100)。输入的最后一行将包含 x (1 ≤ x ≤ 100) - 填字游戏中某个位置可以使用的最大次数。
输出
输出单个整数 - 您可以获得的最大点数。
示例
输入 #1
6 abacba 2 aba 6 ba 3 3
输出 #1
12
注意
例如,对于字符串“abacba”、单词“aba”(6 分)和“ba”(3 分)以及 x = 3,您最多可以获得 12 分 - 单词“aba”出现一次(“abacba”),而“ba”出现两次(“abacba”)。请注意,对于 x = 1,您最多可以获得 9 分,因为您无法同时计算“aba”和“ba”的第一次出现。