CF696D Legen...

Barney 最近和 Nora 一直在一起，他觉得自己可能喜欢上了她。Barney 想发一条肉麻的短信给 Nora，希望让她尽可能开心。 一开始，Nora 的幸福值为 $0$。Nora 喜欢一些类似 “I'm falling for you” 的土味情话。Nora 一共知道 $n$ 条情话，这些情话都是由小写英文字母组成的字符串，其中有些情话可能完全相同（写法相同，但发音或含义可能不同）。每当 Nora 在 Barney 的短信中看到第 $i$ 条情话作为连续子串出现一次时，她的幸福值就会增加 $a_{i}$。这些子串可以重叠，比如，在短信“aaab”中，情话“aa”出现了两次，情话“ab”出现了一次。 由于聊天应用的限制，Barney 的短信最多可以包含 $l$ 个字符。 Barney 想请你帮他让 Nora 尽可能开心。你能帮他做到吗？This is gonna be legen...

输入的第一行包含两个整数 $n$ 和 $l$（$1 \leq n \leq 200, 1 \leq l \leq 10^{14}$）——情话的数量以及 Barney 的短信最大长度。 第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$1 \leq a_{i} \leq 100$），表示每当 Nora 看到第 $i$ 条情话时，她的幸福值会增加 $a_{i}$。 接下来的 $n$ 行，每行一个字符串 $s_{i}$，即第 $i$ 条情话，仅由小写英文字母组成。所有情话字符串的总长度不超过 $200$。 所有字符串均非空。

输出一个整数，表示在 Barney 的短信长度不超过 $l$ 的前提下，Nora 的最大可能幸福值。

第一个样例的最优答案是“hearth”，其中每条情话都恰好出现一次。 第二个样例的最优答案是“artart”。 由 ChatGPT 5 翻译