문제
태현이는 회문(palindrome)을 좋아한다. 회문이란 앞에서부터 읽거나 뒤에서 부터 읽을 경우 동일한 문자열을 뜻한다. 예를 들어 "racecar", "noon", "w"는 회문이며, "computer", "moon", "oh"는 그렇지 않다.
태현이는 주어진 단어를 회문으로 바꾸려고 하는데 다음과 같이 3가지 명령으로 회문으로 바꿀 수 있다.
- "add c x" : 단어에 임의의 글자 c 를 추가한다(단어의 앞 이나 뒤에도 가능하다). 이때 드는 비용은 x다.
- "erase c x ": 단어 내의 c 글자를 제거한다. 이 때 드는 비용은 x다.
- "change c1 c2 x": 단어 내의 c1 글자를 c2 글자로 바꾼다.이때 드는 비용은 x다.
주어진 단어를 회문으로 바꿀 때 비용의 합을 최소화 해서 회문으로 바꾸고자 한다. 회문으로 바꿀 때 드는 비용을 최소화 하는 프로그램을 작성하라.
입력
입력의 첫 줄에는 길이가 50이하인 문자열 S가 입력된다. 문자열은 알파벳 소문자로만 이뤄져있다. 그 다음 줄에는 사용 가능한 명령의 수 C가 입력된다. C는 0이상 50이하의 숫자다. 그 다음줄 부터 C개의 줄에는 명령이 입력되며, 형식은 위에 설명한 형식과 동일하다. 명령을 위해 사용하는 문자는 알파벳 소문자만 입력되며, 비용은 1이상 100,000이하의 정수다.
출력
입력된 문자열 S를 주어진 명령을 이용하여 바꿀 때 드는 최소 비용의 합을 출력한다. 회문으로 바꿀 수 없는 경우는 입력되지 않는다고 가정한다.
예제 #1
topcoder
7
erase t 1
erase o 1
erase p 1
erase c 1
erase d 1
erase e 1
erase r 1
5
예제 #2
caaaaaab
6
change b a 100000
change c a 100000
change c d 50000
change b e 50000
erase d 50000
erase e 49999
199999
힌트
로그인해야 코드를 작성할 수 있어요.