Bubble Cup V9 B Underfail

Points: 20

Time limit: 2.0s

Memory limit: 256M

Problem type

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 a string of length $N$ ~N~ and $M$ ~M~ words, none of which is longer than $K$ ~K~. You are also given an array $P[\,]$ ~P[\,]~ which designates how much each word is worth – the $i^\text{th}$ ~i^\text{th}~ word is worth $P[i]$ ~P[i]~ points.

Whenever you find one of the $M$ ~M~ words in the string, you are given the corresponding number of points. Each letter in the crossword can be used at most $X$ ~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 letters more than $X$ ~X~ times).

In order to solve the puzzle, you need to tell Sanz what's the maximum achievable number of points in the crossword.

Input Specification

The first line of input will contain one integer $N$ ~N~ – the length of the crossword, and the second line will contain the crossword string. The third line will contain the integer $M$ ~M~ – the number of given words, and the next $M$ ~M~ lines will contain descriptions of words: each line will have a word string and an integer $P$ ~P~. The last line of the input will contain $X$ ~X~ – the maximal number of times a position in the crossword can be used.

Output Specification

Output a single integer – the maximal number of points you can get.

Constraints

$1 \le N \le 500$ ~1 \le N \le 500~
$1 \le M \le 100$ ~1 \le M \le 100~
$1 \le X \le 100$ ~1 \le X \le 100~
$1 \le K \le 500$ ~1 \le K \le 500~
$0 \le p \le 100$ ~0 \le p \le 100~

Sample Input

6
abacba
2
aba 6
ba 3
3

Sample Output

Explanation

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

Comments

-5

hezeyu2007001 commented on Sept. 9, 2017, 12:30 a.m.

The skeletons' real names are Sans and Papyrus.

This comment is hidden due to too much negative feedback. Show it anyway.

-1

hezeyu2007001 commented on Sept. 9, 2017, 12:29 a.m.

OMG THIS IS A REFRENCE TO THE GAME UNDERTALE

3

echofox commented on March 27, 2018, 12:58 a.m.

who would've known 🤔