题目背景

小红是一名自媒体编辑，她刚刚写完了一篇长达数万字的初稿文章（视为一个超长字符串 $S$）。

公司的流量算法有一个机制：文章中如果包含了某些"特定热词"，就会获得额外的推荐流量。公司给出了 $N$ 个热门词汇，第 $i$ 个热词长度较短，如果被系统识别到，每次能带来 $val_i$ 的流量。但是，系统识别这个词需要消耗 $w_i$ 的算力。

注意规则：

1. 一个热词能在文章中被识别的最大次数，等于它在初稿文章中实际作为子串出现的次数（允许重叠，比如在 "aaaa" 中，"aa" 出现了 3 次）。
2. 你可以在后台系统里手动勾选激活这些热词，你可以选择激活 1 次、2 次……最多不超过它实际出现的次数。

后台分配给你这篇文章的总算力上限是 $M$。请问如何分配算力，能获得最大的推荐流量？

输入格式

第一行包含一个长字符串 $S$（仅包含小写字母，长度不超过 $10000$）。

第二行包含两个整数 $N, M$，表示热词的数量和总算力上限。

接下来 $N$ 行，每行包含一个热词字符串 $T_i$、耗费算力 $w_i$ 和获得流量 $val_i$。

输出格式

输出一个整数，表示最大能获得的推荐流量。

样例输入

ababaacab
3 10
aba 2 5
ba 1 2
ac 3 10

样例输出

24

数据范围

• $1 \le |S| \le 10000$
• $1 \le N \le 100$
• $1 \le M \le 5000$
• 热词 $T_i$ 长度不超过 20