Description

During a move, Little J found an old typewriter. Out of curiosity, Little J decided to study how to use it. First, you need to insert a paper tape of length $m$ into the typewriter. The typewriter has 26 keys, the lowercase letters a to z. Each time you press a key, the typewriter immediately prints that character on the tape and shifts the tape forward by one unit. Little J quickly mastered how to use this typewriter and wanted to try a new challenge.

He took out a dictionary, chose $n$ words, and assigned a score to each word. Each time a specified word appears in the tape, you gain the corresponding score. For example, if the word eye has score $2$ and year has score $3$, then the tape eyeyeyear has a score of $9$. Little J wants to challenge himself by typing a tape with the highest possible score.

In particular, Little J may occasionally slip and press a character he did not want. Since this old typewriter has no backspace (delete) function, Little J can only accept the mistake and re-plan how to get the highest score under such mistakes. If Little J may press a wrong key at any position, and it is guaranteed that the total number of wrong presses during the whole process does not exceed $k$, please compute the maximum score he can guarantee in the worst case.

Input Format

The first line contains 3 non-negative integers $n, m, k$, representing the number of words, the tape length, and the maximum number of wrong key presses.

The next $n$ lines each contain a string $S$ and a positive integer $a_i$, separated by a space, describing a word and its score.

Output Format

Only one line containing an integer, representing the maximum score in the worst case.

2 4 1
w 1
ha 9

9

Hint

[Sample Explanation]

Below is an incorrect idea:

"There are $4$ cases in total: the 1st position is wrong, the 2nd position is wrong, the 3rd position is wrong, and the 4th position is wrong.

1. If the 1st position is wrong (assume it becomes x, same below), the maximum score is xwha, score $10$.
2. If the 2nd position is wrong, the maximum score is wxha, also $10$.
3. If the 3rd position is wrong, the maximum score is haxw, also $10$.
4. If the 4th position is wrong, the maximum score is hawx, also $10$.

Therefore, in the worst case the maximum score is $10$."

The mistake in this idea is that you cannot decide which key to press first based on which position will be wrong. In other words, you only know which position is wrong after pressing that key. The correct idea is as follows:

1. At position $1$, press h. If it is correct, go to 2; if it is wrong, go to 4.
2. At position $2$, press a. If it is correct, go to 3; if it is wrong, go to 5.
3. At positions $3$ and $4$, both press w, then end. With at most 1 mistake, the final tape is hawx or haxw, score $10$.
4. For the next three positions, press haw in order, then end. Since there will be no more mistakes, the final tape is xhaw, score $10$.
5. For the next two positions, press ha in order, then end. Since there will be no more mistakes, the final tape is hxha, score $9$.

Therefore, in the worst case, the maximum score is $9$.

[Constraints]

Testdata points $1,2$ satisfy $n = 1$ or $k = 0$.

Testdata points $1 \sim 6$ satisfy $n \le 100$, $m \le 500$, $∑|S| \le 500$, $a_i \le 1000$.

Testdata points $7,8$ satisfy $k = 0$, $∑|S| \le 200$.

Testdata points $9,10$ satisfy $∑|S| \le 50$, $a_i \le 1$.

For $100\%$ of the testdata, $n \le 100$, $m \le 10^9$, $∑|S| \le 500$, $a_i \le 1000$, $k \le 5$. Please note that each test point has its own special property.

Translated by ChatGPT 5