문제
농부 창호는 소를 가지고 있는데, 이 소들은 ID들을 가지고 있다. 이 ID들은 M의 길이를 가지며(1≤M≤2,000) N개의(1≤N≤26) 서로 다른 소문자로 구성되어 있다.
우리는 이 ID를 편집해서 앞에서부터 읽으나 뒤에서부터 읽으나 같은(회문) ID로 보이도록 만들고자 한다.
ID의 어떠한 위치에라도 소문자들을 추가할 수도 있고 제거할 수도 있는데, 각각 소문자별로 추가하거나 삭제하는데 드는 비용이 모두 다르다.
우리는 이 비용을 최소화하면서 회문을 만들 때 최소 비용이 얼마인지 알려주는 프로그램을 작성하라.
입력
첫 번째 줄에는 N과 M이 주어진다. 그 다음 두 번째 줄에는 ID가 주어진다. 세 번째 줄부터 N+2개의 줄에는 각각의 줄에 소문자, 해당 소문자의 추가비용, 해당 소문자의 삭제 비용이 순서대로 주어진다.
출력
주어진 ID를 가지고 회문을 만들 경우에 소요되는 최소비용을 출력한다.
예제1
입력
34
abcb
a10001100
b350700
c200800
출력
900
출처
USACO 2007,poj 3280