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

농부 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 태그를 팰린드롬으로 만드는 데 드는 최소 비용을 정수 하나로 출력한다.