题目背景

译自 ROI 2016 Day2 T4. Тренажёр «10_2-пальцевый набор»

题目描述

现代的机器人程序员必须掌握盲打的 $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$。

9 2 8
000110100
1 100
1 11001

4

9 3 10
010110101
3 0101
10 011
2 100

8

3 1 3
100
1 101

-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$			1, 2
4		$m \le 50\,000$				$l_{\text{max}} \le 2000$	1–3
5	10		$n \le 20$			—	—
6	5		$n \le 200$				5
7	9		—		$c_i = 1$		—
8	5				$c_i \le 10$		7
9					$c_i \le 100$		7, 8
10					—		1–9
11		$m \le 100\,000$		$L \le 100\,000$			1–10
12		$m \le 200\,000$		$L \le 200\,000$			1–11
13		$m \le 300\,000$		$L \le 300\,000$			1–12

翻译由 ChatGPT-5 完成