二指禅
题号：NC53349
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

未来的机器人码农一定学过二指禅。为了帮助码农们精通二指禅，某打字软件推出了一种新的练习方法。
屏幕的上半部分会显示一个m位01串S（01串：只包含数字0和1的字符串）。下半部分会显示n个01串（称之为模式串），编号分别为。第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。
示例1

输入

复制 
9 2 8
000110100
1 100
1 11001

输出

复制 
4
示例2

输入

复制 
9 3 10
010110101
3 0101
10 011
2 100

输出

复制 
8
示例3

输入

复制 
3 1 3
100
1 101

输出

复制 
-1

备注:

对于所有数据，；。
设表示单个模式串的最大长度。


感谢LOJ分享，译文来自 https://loj.ac/problem/3067