小 J 在搬家的过程中发现了一台古老的打字机。

好奇的小 J 决定研究如何使用它。首先，需要将一条长度为 $m$ 的纸带放入打字机。打字机上共有 $26$ 个按键，分别是小写字母 a - z。每当你按下一个按键时，打字机就会立即在纸带上打印出那个字符，并将纸带平移一个单位距离。

聪明的小 J 很快就掌握了这款打字机的使用技巧，并想尝试新的挑战。他拿出了一本字典，挑选了 $n$ 个单词，并给每个单词设定了分数。纸带中每出现一次指定的单词，就会得到对应的分数。例如， 单词 eye 的分数为 2， year 的分数为 3，那么纸带 eyeyeyear 的分数为 9 分。小 J 希望挑战自己，打出分数最高的纸带。

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

输入格式

第一行包含 3 个非负整数 n, m, k，分别表示单词数量、纸带长度和最多按错次数。 接下来 n 行，每行为一个字符串 Si和正整数 Ai，由空格隔开，描述一个单词及其得分。

输出格式

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

样例数据

样例输入

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，倘若按对， goto 2，倘若按错， goto 4；
2. 第 2 位按 a，倘若按对， goto 3，倘若按错， goto 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 – 6 满足，$n \le 100$，$m \le 500$，$\sum |S_i| \le 500$，$A_i \le 1\,000$；

测试点 7 – 8 满足，$k = 0$，$\sum |S_i| \le 200$；

测试点 9 – 10 满足，$\sum |S_i| ≤ 50$，$A_i \le 1$。

对于 $100\%$ 的数据，$n \le 100$，$m \le 10^9$，$\sum |S_i| \le 500$，$A_i \le 1\,000$，$k \le 5$。