20527번 - Тренажёр <<$10_2$-пальцевый набор>> 서브태스크다국어

Современный робот-программист должен владеть слепым $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$, если требуемым образом набрать её невозможно.

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