가장 저렴하게 팰린드롬 만들기

면접 대비

시간 제한1초메모리 제한128 MB

요약

문자열과 문자별 삽입 및 삭제 비용이 주어질 때, 아무 위치에나 문자를 넣거나 지워서 팰린드롬으로 만드는 최소 비용을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 문자열, 배열, 수학
정답자: 아직 제출이 없습니다

문제

농부 John은 소들을 관리하기 위해 자동화 시스템을 설치했다. 각 소에는 전자 ID 태그가 달려 있고, 소가 스캐너를 지나갈 때 시스템이 태그를 읽는다. 각 ID 태그는 알파벳 소문자 $N$ 개( $1 \le N \le 26$ ) 중에서 뽑은 문자로 이루어진 길이 $M$ ( $1 \le M \le 2000$ )의 문자열 하나로 되어 있다.

장난기 많은 소들은 가끔 뒤로 걸어서 시스템을 속이려 한다. ID가 abcba인 소는 어느 방향으로 걸어도 같은 문자열로 읽히지만, ID가 abcb인 소는 방향에 따라 서로 다른 두 문자열(abcb와 bcba)로 읽힐 수 있다.

John은 소가 어느 방향으로 지나가도 태그가 같은 문자열로 읽히도록, 즉 앞에서 읽으나 뒤에서 읽으나 똑같은 팰린드롬(회문)이 되도록 ID 태그를 고치고 싶다. 예를 들어 abcb는 끝에 a를 더해 abcba로 만들 수 있고, 앞에 bcb를 더해 bcbabcb로 만들거나 a를 지워 bcb로 만들 수도 있다. 문자열의 어느 위치에서든 문자를 넣거나 뺄 수 있으며, 그 결과 문자열은 원래보다 길어지거나 짧아질 수 있다.

전자 태그이기 때문에 문자 하나를 넣거나 빼는 데에는 비용이 들며, 이 비용은 어떤 문자를 다루느냐에 따라 다르다( $0 \le \text{cost} \le 10000$ ). 각 알파벳 문자를 넣는 비용과 빼는 비용이 주어질 때, ID 태그를 팰린드롬으로 만드는 데 드는 최소 비용을 구하라. 빈 문자열도 앞뒤로 같게 읽히는 것으로 본다. 문자열에는 비용이 정의된 문자만 추가할 수 있다.

입력

첫째 줄: 두 정수 $N$ 과 $M$ 이 공백으로 구분되어 주어진다.
둘째 줄: 처음 ID 문자열을 이루는 정확히 $M$ 개의 문자가 주어진다.
셋째 줄부터 $N+2$ 번째 줄까지: 각 줄에 알파벳 문자 하나와 정수 두 개가 공백으로 구분되어 주어진다. 두 정수는 각각 그 문자를 추가하는 비용과 삭제하는 비용이다.

출력

첫째 줄: ID 태그를 팰린드롬으로 만드는 데 드는 최소 비용을 정수 하나로 출력한다.

예제5

예제 1

입력

3 4
abcb
a 1000 1100
b 350 700
c 200 800

예상 출력

예제 2

입력

3 5
abcba
a 1000 1100
b 350 700
c 200 800

예상 출력

예제 3
입력
```
1 1
a
a 5 7
```
예상 출력
```
0
```
예제 4
입력
```
1 2
aa
a 5 7
```
예상 출력
```
0
```
예제 5
입력
```
2 2
ab
a 100 200
b 50 300
```
예상 출력
```
50
```