3067 「ROI 2016 Day2」二指禅

**译自 [ROI 2016](http://neerc.ifmo.ru/school/archive/2015-2016.html) Day2 T4.** ***[Тренажёр «10₂-пальцевый набор»](http://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-roi-2016-day2.pdf)*** 未来的机器人码农一定学过二指禅。为了帮助码农们精通二指禅，某打字软件推出了一种新的练习方法。 屏幕的上半部分会显示一个 $m$ 位 01 串 $S$（01 串：只包含数字 0 和 1 的字符串）。下半部分会显示 $n$ 个 01 串（称之为模式串），编号分别为 $1\ldots n$。第 $i$ 个模式串为 $w_i$。每个模式串有一个费用 $c_i$。模式串的总长度为 $L$。 你需要将 $S$ 分成若干个子串，使得对于 $S$ 的每个子串 $S_i$，存在一个 $j$ 满足：$S_i$ 是 $c_j$ 的前缀或后缀。 划分的总花费就是每个子串对应的模型的模式串之和。试求最小总花费。如果没有合法划分方案，则输出 `-1`。

对于所有数据，$1 ⩽ m, n, L ⩽ 300\,000$；$1 ⩽ c_i ⩽ 10^9$。

设 $l_{max}$ 表示单个模式串的最大长度。

子任务 #	分值	$m$	$n$	$L$	$c_i$	$l_{max}$	依赖子任务
1	20	$m \le 50$	$n \le 50$	$L \le 500$	$c_i \le 1000$	$l_{max} \le 50$
2	10	$m \le 5000$	---	$L \le 5000$	---	$l_{max} \le 1000$	1
3	8	$m \le 10\,000$	---	$L \le 50\,000$	---	$l_{max} \le 1000$	1, 2
4	8	$m \le 50\,000$	---	$L \le 50\,000$	---	$l_{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