该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$Oasis$ 的老师非常厉害，今天要教学生们如何作曲。

小 $G$ 在课上学的津津有味并且跃跃欲试，老师为了降低难度，于是给了小 $G$ 一个模板旋律，和一个乐章库，只须将其划分获得一个乐章即可。

整个谱曲的过程如下：

• 给定一个长度为 $m$ 的 $01$ 串 $A$，$n$ 个总长度为 $L$ 的 $01$ 串 $B_i$，长度为 $n$ 的数列 $c_i$。

• 小 $G$ 如何谱写一首乐章： 需要给出一个数列 $a_1,a_2,...,a_k(1\leq a_i \leq n)$，以及将 $A$ 从左到右拆分成 $k$ 个非空字符串的一种方案 $S_1, \ldots, S_k$，使得所有 $i = 1, \ldots, k$ 都满足 $S_i$ 是 $B_{a_i}$ 的前缀或后缀。

• 对于满足条件的数列 $a_i$，定义其不和谐度为 $\sum_{i=1}^{k} c_{a_i}$。

请求出最小的不和谐度的乐章方案。若不存在满足要求的数列 $a_i$ 和划分 $S_i$ 则输出 $-1$。

输入格式

第一行三个正整数 $m, n, L$ 分别表示 $A$ 的长度，$B$ 的个数，$B$ 的总长。

第二行一个长度为 $m$ 的 $01$ 串表示 $A$。

接下来 $n$ 行，每行一个正整数 $c_i$ 和一个 $01$ 串 $B_i$。

输出格式

输出一行一个正整数表示最小的违和度，或 $−1$ 表示无解。

样例

样例输入 #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

见考生文件夹中的下发大样例/song/song3.in

样例输出 #3

见考生文件夹中的下发大样例/song/song3.ans

样例输入 #4

见考生文件夹中的下发大样例/song/song4.in

样例输出 #4

见考生文件夹中的下发大样例/song/song4.ans

样例解释

样例 #1 解释

样例一的一组解：$k = 4, a = \{1, 1, 2, 1\}, S = \{$00$,$0$,$110$,$100$\}$

样例 #2 解释

样例二的一组解：$k = 3, a = \{1, 3, 1\}, S = \{$0101$,$1$,$0101$\}$

样例 #3 解释

样例符合测试点 $9\sim 10$。

样例 #4 解释

样例符合测试点 $15\sim 18$。

数据范围

对于 $100\%$ 的数据我们有 $1 \leq m,n,L \leq 2 \times 10^5, 1 \leq c_i \leq 10^9$。

设 $l_{max}$ 为 $B$ 中字符串长度的最大值。