题目描述

小 J 在搬家的过程中发现了一台古老的打字机。 好奇的小 J 决定研究如何使用它。首先，需要将一条长度为 $m$ 的纸带放入打字机。打字机上共有 26 个按键，分别是小写字母 a 到 z 。每当你按下一个按键时，打字机 就会立即在纸带上打印出那个字符，并将纸带平移一个单位距离。聪明的小 J 很快就掌握了这款打字机的使用技巧，并想尝试新的挑战。

他拿出了一本字典，挑选了 $n$ 个单词，并给每个单词设定了分数。纸带中每出现一次指定的单词，就会得到对应的分数。例如， 单词 eye 的分数为 $2$， year 的分数为 $3$，那么纸带 eyeyeyear 的分数为 $9$ 分。小 J 希望挑战自己，打出分数最高的纸带。

特别地，小 J 偶尔会手抖，按到自己不想输入的字符。由于这台古老的打字机没有退格（删除）功能，所以小 J 只能接受按错这个事实，重新规划在按错的情况下如何得最高分。倘若小 J 有可能在任意位置按错按键，并保证整个过程中按错的次数不超过 $k$ 次，那么请你算出他在最坏情况下的最高得分是多少。

输入格式

第一行包含 3 个非负整数 $n, m, k$，分别表示单词数量、纸带长度和最多按错次数。

接下来 $n$ 行，每行为一个字符串 $S$ 和正整数 $a_i$，由空格隔开，描述一个单词及其得分。

输出格式

仅一行，包含一个整数，表示最坏情况下的最大得分。

2 4 1
w 1
ha 9

9

提示

【样例解释】

以下是一种错误思路：

"共 $4$ 种情况，即第 $1$ 位按错、第 $2$ 位按错、第 $3$ 位按错和第 $4$ 位按错。

1. 第 $1$ 位按错（不妨假设按成 x，下同），最高得分为 xwha，得分为 $10$。
2. 第 $2$ 位按错，最高得分为 wxha，同样为 $10$ 分。
3. 第 $3$ 位按错，最高得分为 haxw，同样为 $10$ 分。
4. 第 $4$ 位按错，最高得分为 hawx，同样为 $10$ 分。

综上，最坏情况下最高得分为 $10$ 分。"

这种思路的错误之处在于，你不能根据哪一位按错决定你第一位按哪个键。 换种说法，你在哪一位按错，是在按下那个按键之后才能知道的事情。 正确的思路如下：

1. 第 $1$ 位先按 h，倘若按对， 跳至 2，倘若按错， 跳至 4；
2. 第 $2$ 位按 a，倘若按对， 跳至 3，倘若按错， 跳至 5；
3. 第 $3$ 位和第 $4$ 位都按 w， 结束。 至多错 1 次，最终纸带为 hawx 或 haxw，得分为 $10$ 分。
4. 后面三位依次按 haw， 结束。 因为不会再错， 最终纸带为 xhaw，得分为 $10$ 分。
5. 后面两位依次按 ha， 结束。因为不会再错， 最终纸带为 hxha，得分为 $9$ 分。

综上，最坏情况下，最高得分为 $9$ 分。

【数据范围】

测试点 $1,2$ 满足，$n = 1$ 或 $k = 0$；

测试点 $1\sim 6$ 满足，$n ≤ 100$，$m ≤ 500$，$∑|S| ≤ 500$，$a_i ≤1000$；

测试点 $7,8$ 满足，$k = 0$，$∑|S| ≤ 200$；

测试点 $9,10$ 满足，$∑|S| ≤ 50$，$a_i ≤1$。

对于 $100\%$ 的数据，$n ≤ 100$，$m ≤ 10^9$ ，$∑|S| ≤ 500$，$a_i ≤1000$，$k ≤ 5$。请注意，每一个测试点都有相应特殊性质。