Задача №113224. Тренажёр «\(10_2\)-пальцевый набор»
Современный робот-программист должен владеть слепым \(10_2\)-пальцевым методом набора бинарных строк, состоящих из символов «0» и «1». В инновационном тренажёре, созданном специально для уже освоивших \(10_2\)-пальцевый набор роботов, предлагается следующее упражнение. В верхней части экрана выводится строка, состоящая из нулей и единиц. Ниже выводятся пары \((c_i, w_i)\), каждая из которых состоит из бинарного слова \(w_i\) и его стоимости \(c_i\) — количества штрафных баллов, начисляемых за каждое использование слова \(w_i\) при наборе строки.
Робот должен набрать заданную строку в виде последовательности записанных подряд префиксов или суффиксов предложенных ему бинарных слов. Одно и то же слово можно использовать произвольное количество раз, но за каждое использование префикса или суффикса начисляются штрафные баллы, равные стоимости этого слова.
Префиксом слова называется последовательность подряд идущих символов этого слова, начинающаяся с первого символа слова, а суффиксом — последовательность подряд идущих символов этого слова, заканчивающаяся последним символом слова. Слово целиком является как своим префиксом, так и своим суффиксом.
Требуется написать программу, которая вычисляет минимально возможное суммарное количество штрафных баллов, начисляемых роботу за набор заданной строки с использованием префиксов и суффиксов предложенных бинарных слов, или определяет, что строку набрать невозможно.
Первая строка входных данных содержит три целых числа \(m\), \(n\) и \(L\) — длину заданной строки, количество слов, префиксы и суффиксы которых можно использовать при её наборе, и суммарную длину этих слов (\(1 \le m \le 300 000; 1 \le n \le 300 000; 1 \le L \le 300 000\)).
Во второй строке находится заданная строка, состоящая из m символов «0» или «1». Следующие \(n\) строк описывают предлагаемые для использования бинарные слова. Сначала указывается целая стоимость слова в штрафных баллах \(c_i\) (\(1 \le c_i \le 10^9\) ). Затем в той же строке через пробел следует непустое слово, состоящее из символов «0» или «1» Длина каждого слова не превосходит значения \(l_{max}\), дополнительные ограничения на которое накладываются в некоторых подзадачах.
Выходные данные должны содержать одно целое число — минимальное количество штрафных баллов, которое потребуется, чтобы набрать заданную строку, или число −1, если требуемым образом набрать её невозможно.
В таблице системы оценивания этой задачи указаны только дополнительные ограничения, накладываемые на различные параметры входных данных. Значение \(l_{max}\) задает максимальную длину каждого из предложенных роботу бинарных слов, префиксы и суффиксы которых он может использовать.
В первом примере можно сначала набрать суффикс первого слова длины два, затем его же суффикс длины один, далее префикс второго слова длины три после чего первое слово целиком.
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