31092번 - 스티커 재배치

문제

1ドル$번 스티커부터 $M$번 스티커까지 총 $M$종류의 스티커가 있다. $j$번 스티커에는 알파벳 소문자 $s_j$가 적혀 있다. 이때 같은 알파벳이 적힌 스티커가 여러 종류 있을 수 있다.

여러분은 $N$개의 칸으로 나누어진 보드판을 하나 갖고 있다. 각 칸에는 스티커가 하나씩 붙어 있고, $i$번째 칸에는 $b_i$번 스티커가 붙어 있다. 같은 종류의 스티커가 여러 개의 칸에 붙어 있는 것도 가능하다. 1ドル$번째 칸에 있는 스티커부터 $N$번째 칸에 있는 스티커까지 적힌 알파벳을 순서대로 읽으면 알파벳 소문자로 구성된 길이가 $N$인 문자열을 하나 얻는다. 이를 스티커 문자열이라고 정의한다.

여러분은 다음 시행을 통해 스티커 문자열을 바꿀 수 있다. 모든 시행을 완료하였을 때, 보드판에 빈칸이 있으면 안 된다.

• 스티커가 붙어 있는 칸의 스티커를 뗄 수 있다. 스티커는 강력 접착제로 붙어있기 때문에, $j$번 스티커를 떼는 데에는 $d_j$만큼의 비용이 든다. 스티커를 뗀 칸은 빈칸이 된다.
• 빈칸을 하나 골라서 스티커를 붙일 수 있다. 이때, 스티커를 새로 구매하여 붙이거나 이미 떼었던 스티커를 재활용하여 붙이는 것이 가능하다. 스티커를 붙일 때는 비용이 발생하지 않으며, $j$번 스티커를 한 장 구매하는 데에는 $a_j$만큼의 비용이 든다. 같은 종류의 스티커를 여러 장 구매하는 것도 가능하다.

여러분의 목표는, 적절하게 시행을 반복하여 스티커 문자열이 입력으로 주어진 길이가 $K(\leq N)$인 문자열 $S$를 부분 문자열로 포함하도록 만드는 것이다. 그러기 위한 최소 비용을 구하여라.

입력

첫 번째 줄에 정수 $N,ドル $M,ドル $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$개의 줄에 걸쳐 스티커의 정보가 주어진다. 그중 $j$번째 줄에는 $j$번 스티커의 정보 $s_j,ドル $d_j,ドル $a_j$가 공백으로 구분되어 주어진다.

그다음 줄에 $N$개의 정수 $b_1,\cdots ,b_N$이 공백으로 구분되어 주어진다. $b_i$는 보드판의 $i$번째 칸에 있는 스티커의 번호를 의미한다.

그다음 줄에 길이가 $K$인 알파벳 소문자로 구성된 문자열 $S$가 주어진다.

출력

스티커 문자열이 $S$를 부분 문자열로 포함하도록 만드는 데 필요한 최소 비용을 출력한다. 만약 $S$를 부분 문자열로 포함하도록 만들 수 없다면 -1을 출력한다.

제한

• 1ドル\le N,M\le 500$
• 1ドル\le K\le N$
• $s_j$는 알파벳 소문자이다. $(1 \leq j \leq M)$
• 1ドル\le d_j,a_j\le 1,円 000$ (1ドル\le j\le M$)
• 1ドル\le b_i\le M$ (1ドル\le i\le N$)

노트

문자열 $T$의 부분 문자열이란, 문자열 $T$에서 연속된 일부분에 해당하는 문자열을 의미한다. 예를 들어 문자열 $T$가 "goodbyeboj"이라면 "goo", "db", "j"는 $T$의 부분 문자열이고, "a", "god", "job"는 $T$의 부분 문자열이 아니다.