#3067. 「ROI 2016 Day2」二指禅

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

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

未来的机器人码农一定学过二指禅。为了帮助码农们精通二指禅,某打字软件推出了一种新的练习方法。

屏幕的上半部分会显示一个 m 位 01 串 S (01 串:只包含数字 0 和 1 的字符串)。下半部分会显示 n 个 01 串(称之为模式串),编号分别为 1\ldots n 。第 i 个模式串为 c_i 。每个模式串有一个费用 w_i 。模式串的总长度为 L

你需要将 S 分成若干个子串,使得对于 S 的每个子串 S_i ,存在一个 j 满足: S_i c_j 的前缀或后缀。

划分的总花费就是每个子串对应的模型的模式串之和。试求最小总花费。如果没有合法划分方案,则输出 -1

输入格式

m,n,L
S
c_i,w_i

样例

样例输入 1

9 2 8
000110100
1 100
1 11001

样例输出 1

4

样例输入 2

9 3 10
010110101
3 0101
10 011
2 100

样例输出 2

8

样例输入 3

3 1 3
100
1 101

样例输出 3

-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 1, 2
4  8  m \le 50\,000 l_{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  5  c_i\le 100 7, 8
10 5 --- 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