题目描述

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

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

屏幕的上半部分会显示一个 $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

4

9 3 10
010110101
3 0101
10 011
2 100

8

3 1 3
100
1 101

-1

数据范围与提示

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

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