| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 65 | 4 | 4 | 6.897% |
Современный робот-программист должен владеть слепым 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,ドル если требуемым образом набрать её невозможно.
В таблице системы оценивания этой задачи указаны только дополнительные ограничения, накладываемые на различные параметры входных данных. Значение $l_{max}$ задает максимальную длину каждого из предложенных роботу бинарных слов, префиксы и суффиксы которых он может использовать.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $m \le 50,ドル $n \le 50,ドル $L \le 500,ドル $c_i \le 1000,ドル $l_{max} \le 50$ |
| 2 | 10 | $m \le 5000,ドル $L \le 5000,ドル $l_{max} \le 1000$ |
| 3 | 8 | $m \le 10,000円,ドル $L \le 50,000円,ドル $l_{max} \le 1000$ |
| 4 | 8 | $m \le 50,000円,ドル $L \le 50,000円,ドル $l_{max} \le 2000$ |
| 5 | 10 | $m \le 50,000円,ドル $n \le 20,ドル $L \le 50,000円$ |
| 6 | 5 | $m \le 50,000円,ドル $n \le 200,ドル $L \le 50,000円$ |
| 7 | 9 | $m \le 50,000円,ドル $L \le 50,000円,ドル $c_i=1$ |
| 8 | 5 | $m \le 50,000円,ドル $L \le 50,000円,ドル $c_i\le 10$ |
| 9 | 5 | $m \le 50,000円,ドル $L \le 50,000円,ドル $c_i\le 100$ |
| 10 | 5 | $m \le 50,000円,ドル $L \le 50,000円$ |
| 11 | 5 | $m \le 100,000円,ドル $L \le 100,000円$ |
| 12 | 5 | $m \le 200,000円,ドル $L \le 200,000円$ |
| 13 | 5 | $m \le 300,000円,ドル $L \le 300,000円$ |
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
В первом примере можно сначала набрать суффикс первого слова длины два, затем его же суффикс длины один, далее префикс второго слова длины три после чего первое слово целиком.