P14212 [ROI 2016 Day2] 二进制输入

**译自 [ROI 2016](http://neerc.ifmo.ru/school/archive/2015-2016.html) Day2 T4.** ***[Тренажёр «10_2-пальцевый набор»](http://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-roi-2016-day2.pdf)***

现代的机器人程序员必须掌握盲打的 $10_2$ 指法，用以输入只由字符 **0** 和 **1** 组成的二进制字符串。在专为已经熟练掌握 $10_2$ 指法的机器人设计的创新训练器中，提出了如下练习。 屏幕上方显示一个由 0 和 1 组成的目标字符串。屏幕下方给出若干对 $(c_i, w_i)$，其中 $w_i$ 是一个二进制单词，$c_i$ 是其**代价**——表示每次在输入目标字符串时使用该单词所需的罚分。 机器人需要将给定的目标字符串输入出来。它可以使用提供的二进制单词的**前缀**或**后缀**，并将它们依次拼接起来。同一个单词可以被使用任意多次。但每次使用该单词的前缀或后缀时，都会获得等于该单词代价 $c_i$ 的罚分。 一个单词的**前缀**是从单词第一个字符开始的连续字符序列，一个单词的**后缀**是以单词最后一个字符结尾的连续字符序列。整个单词既是它的前缀，也是它的后缀。 请编写一个程序，计算在使用所给单词的前缀和后缀拼接出目标字符串时，机器人所能获得的**最小总罚分**。若无法构造出目标字符串，则输出 $-1$。

输入的第一行包含三个整数 $m$、$n$ 和 $L$——分别表示目标字符串的长度、可使用的单词数量，以及这些单词长度的总和（$1 \le m \le 300\,000$；$1 \le n \le 300\,000$；$1 \le L \le 300\,000$）。 第二行包含目标字符串，由 $m$ 个字符组成，每个字符为 **0** 或 **1**。 接下来的 $n$ 行中，每行描述一个可使用的二进制单词。首先给出该单词的罚分 $c_i$（$1 \le c_i \le 10^9$），然后是一个非空的二进制字符串 $w_i$（仅由 **0** 和 **1** 组成），二者以空格分隔。 每个单词的长度不超过 $l_{\max}$，该值在不同子任务中有额外限制。

输出一个整数——输入目标字符串所需的最小罚分总和；如果无法通过给定的单词前缀或后缀组合出目标字符串，则输出 $-1$。

### 样例解释 在第一个样例中，可以按以下方式获得目标字符串： 1. 使用第一个单词的后缀（长度为 2）； 2. 再次使用第一个单词的后缀（长度为 1）； 3. 使用第二个单词的前缀（长度为 3）； 4. 最后使用第一个单词的完整形式。 总罚分为 4。 ### 评分说明 下表列出了各子任务中对输入参数的附加限制。其中 $l_{\text{max}}$ 表示提供给机器人的每个二进制单词的最大长度。 | 子任务编号 | 分值 | $m$ | $n$ | $L$ | $c_i$ | $l_{\text{max}}$ | 必须通过的子任务 | |:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:| | 1 | 20 | $m \le 50$ | $n \le 50$ | $L \le 500$ | $c_i \le 1000$ | $l_{\text{max}} \le 50$ | — | | 2 | 10 | $m \le 5000$ | — | $L \le 5000$ | — | $l_{\text{max}} \le 1000$ | 1 | | 3 | 8 | $m \le 10\,000$ | — | $L \le 50\,000$ | — | $l_{\text{max}} \le 1000$ | 1, 2 | | 4 | 8 | $m \le 50\,000$ | — | $L \le 50\,000$ | — | $l_{\text{max}} \le 2000$ | 1–3 | | 5 | 10 | $m \le 50\,000$ | $n \le 20$ | $L \le 50\,000$ | — | — | — | | 6 | 5 | $m \le 50\,000$ | $n \le 200$ | $L \le 50\,000$ | — | — | 5 | | 7 | 9 | $m \le 50\,000$ | — | $L \le 50\,000$ | $c_i = 1$ | — | — | | 8 | 5 | $m \le 50\,000$ | — | $L \le 50\,000$ | $c_i \le 10$ | — | 7 | | 9 | 5 | $m \le 50\,000$ | — | $L \le 50\,000$ | $c_i \le 100$ | — | 7, 8 | | 10 | 5 | $m \le 50\,000$ | — | $L \le 50\,000$ | — | — | 1–9 | | 11 | 5 | $m \le 100\,000$ | — | $L \le 100\,000$ | — | — | 1–10 | | 12 | 5 | $m \le 200\,000$ | — | $L \le 200\,000$ | — | — | 1–11 | | 13 | 5 | $m \le 300\,000$ | — | $L \le 300\,000$ | — | — | 1–12 | 翻译由 ChatGPT-5 完成