Тренажёр << $10_2$ -пальцевый набор>>

시간 제한3초메모리 제한512 MB

요약

주어진 이진 문자열을 각 단어의 접두사나 접미사 조각으로 잘라 붙이면서 단어마다 정해진 비용을 지불할 때, 전체 비용의 최솟값을 구하거나 불가능하면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 문자열 매칭, 트라이, 최단 경로
정답자: 아직 제출이 없습니다

문제

Современный робот-программист должен владеть слепым $10\_2$ -пальцевым методом набора бинарных строк, состоящих из символов <<0>> и <<1>>. В инновационном тренажёре, созданном специально для уже освоивших $10\_2$ -пальцевый набор роботов, предлагается следующее упражнение. В верхней части экрана выводится строка, состоящая из нулей и единиц. Ниже выводятся пары ( $c\_i$ ,~ $w\_i$ ), каждая из которых состоит из бинарного слова $w\_i$ и его стоимости $c\_i$ --- количества штрафных баллов, начисляемых за каждое использование слова $w\_i$ при наборе строки.

Робот должен набрать заданную строку в виде последовательности записанных подряд префиксов или суффиксов предложенных ему бинарных слов. Одно и то же слово можно использовать произвольное количество раз, но за каждое использование префикса или суффикса начисляются штрафные баллы, равные стоимости этого слова.

Префиксом слова называется последовательность подряд идущих символов этого слова, начинающаяся с первого символа слова, а суффиксом --- последовательность подряд идущих символов этого слова, заканчивающаяся последним символом слова. Слово целиком является как своим префиксом, так и своим суффиксом.

Требуется написать программу, которая вычисляет минимально возможное суммарное количество штрафных баллов, начисляемых роботу за набор заданной строки с использованием префиксов и суффиксов предложенных бинарных слов, или определяет, что строку набрать невозможно.

입력

Первая строка входных данных содержит три целых числа $m$ , $n$ и $L$ --- длину заданной строки, количество слов, префиксы и суффиксы которых можно использовать при её наборе, и суммарную длину этих слов ( $1 \leq m \leq 300\\,000$ ; $1 \leq n \leq 300\\,000$ ; $1 \leq L \leq 300\\,000$ ).

Во второй строке находится заданная строка, состоящая из $m$ символов <<0>> или <<1>>. Следующие $n$ строк описывают предлагаемые для использования бинарные слова. Сначала указывается целая стоимость слова в штрафных баллах $c\_i$ ( $1 \leq c\_i \leq 10^9$ ). Затем в той же строке через пробел следует непустое слово, состоящее из символов <<0>> или <<1>> Длина каждого слова не превосходит значения $l\_{max}$ , дополнительные ограничения на которое накладываются в некоторых подзадачах.

출력

Выходные данные должны содержать одно целое число --- минимальное количество штрафных баллов, которое потребуется, чтобы набрать заданную строку, или число $-1$ , если требуемым образом набрать её невозможно.

힌트

В первом примере можно сначала набрать суффикс первого слова длины два, затем его же суффикс длины один, далее префикс второго слова длины три после чего первое слово целиком.

예제3

예제 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
```