Little J discovered an ancient typewriter while moving.

Curious, Little J decided to study how to use it. First, a paper tape of length $m$ must be inserted into the typewriter. The typewriter has 26 keys, corresponding to the lowercase letters a through z. Every time you press a key, the typewriter immediately prints that character on the tape and advances the tape by one unit of distance.

The clever Little J quickly mastered the techniques of this typewriter and wanted to try a new challenge. He took out a dictionary, selected $n$ words, and assigned a score to each word. Every time a specified word appears on the tape, the corresponding score is awarded. For example, if the word eye has a score of 2 and year has a score of 3, then the tape eyeyeyear scores 9 points. Little J wants to challenge himself to produce the tape with the highest possible score.

In particular, Little J occasionally has shaky hands and presses a character he did not intend to input. Since this ancient typewriter has no backspace (delete) function, Little J must accept the fact that he made a mistake and re-plan how to achieve the highest score under the condition of making mistakes. If it is possible for Little J to press the wrong key at any position, and he is guaranteed that the total number of mistakes made during the entire process will not exceed $k$, please calculate his maximum possible score in the worst-case scenario.

Input

The first line contains 3 non-negative integers $n, m, k$, representing the number of words, the length of the tape, and the maximum number of mistakes allowed, respectively. The next $n$ lines each contain a string $S_i$ and a positive integer $A_i$, separated by a space, describing a word and its score.

Output

A single line containing an integer representing the maximum score in the worst-case scenario.

Examples

Input 1

2 4 1
w 1
ha 9

Output 1

9

Note

First, here is an incorrect line of reasoning:

There are 4 possible scenarios: a mistake at the 1st position, 2nd position, 3rd position, or 4th position.

1. Mistake at the 1st position (assume it is pressed as x, same below), the maximum score is xwha, score is 10.
2. Mistake at the 2nd position, the maximum score is wxha, also 10 points.
3. Mistake at the 3rd position, the maximum score is haxw, also 10 points.
4. Mistake at the 4th position, the maximum score is hawx, also 10 points.

In summary, the maximum score in the worst case is 10 points.

The flaw in this reasoning is that you cannot decide which key to press first based on which position you will make a mistake in. In other words, you only know where you made a mistake after you have pressed the key.

The correct reasoning is as follows:

1. Press h for the 1st position. If correct, go to 2; if incorrect, go to 4.
2. Press a for the 2nd position. If correct, go to 3; if incorrect, go to 5.
3. Press w for both the 3rd and 4th positions, then finish. With at most 1 mistake, the final tape is hawx or haxw, scoring 10 points.
4. Press haw for the remaining three positions, then finish. Since no more mistakes will occur, the final tape is xhaw, scoring 10 points.
5. Press ha for the remaining two positions, then finish. Since no more mistakes will occur, the final tape is hxha, scoring 9 points.

In summary, in the worst-case scenario, the maximum score is 9 points.

Subtasks

Test cases 1 – 2 satisfy $n = 1$ or $k = 0$.

Test cases 1 – 6 satisfy $n \le 100$, $m \le 500$, $\sum |S_i| \le 500$, $A_i \le 1\,000$.

Test cases 7 – 8 satisfy $k = 0$, $\sum |S_i| \le 200$.

Test cases 9 – 10 satisfy $\sum |S_i| \le 50$, $A_i \le 1$.

For 100% of the data, $n \le 100$, $m \le 10^9$, $\sum |S_i| \le 500$, $A_i \le 1\,000$, $k \le 5$.