문자열의 마법
시간 제한8초메모리 제한512 MB
삽입, 삭제, 교체, 첫 글자를 끝으로 옮기는 연산의 비용이 주어질 때 X를 Y로 바꾸는 최소 비용을 구한다.
문제
마법사인 당신은 오늘도 마법 수련에 힘쓰고 있다. 당신은 지금 영소문자로 이루어진 문자열 X 를 가지고 있다. 오늘 수련 과제는 이 문자열을 다른 문자열 Y 로 바꾸는 것이다.
당신은 문자열을 바꾸는 마법을 4 종류 익혔고, 그것들을 원하는 순서로 몇 번이든 외울 수 있다. 다만 마법을 외울 때마다 마법석이라는 특별한 돌을 소비한다. 당신이 익힌 마법은 다음과 같다.
- 마법석을 A 개 소비한다. 가지고 있는 문자열의 원하는 위치에 원하는 영소문자 1 글자를 추가한다. 예를 들어 원래 문자열이 bcbd였다면 abcbd, bcebd, bcbdf 등으로 바꿀 수 있다.
- 마법석을 E 개 소비한다. 가지고 있는 문자열의 원하는 1 글자를 제거한다. 예를 들어 원래 문자열이 bcbd였다면 cbd, bbd, bcd, bcb 중 하나로 바꿀 수 있다. 원래 문자열의 길이가 0이라면 이 마법을 외울 수 없다.
- 마법석을 S 개 소비한다. 가지고 있는 문자열의 원하는 1 글자를 다른 원하는 영소문자 1 글자로 바꾼다. 예를 들어 원래 문자열이 bcbd였다면 acbd나 bebd 등으로 바꿀 수 있다. 원래 문자열의 길이가 0이라면 이 마법을 외울 수 없다.
- 마법석을 R 개 소비한다. 가지고 있는 문자열의 맨 앞 1 글자를 맨 뒤로 옮긴다. 예를 들어 원래 문자열이 bcbd였다면 cbdb로 바꿀 수 있다. 원래 문자열의 길이가 0이라면 이 마법을 외울 수 없다.
마법석은 비싸므로 당신은 마법석 소비를 최소한으로 줄이려 한다. 문자열 X 를 문자열 Y 로 바꾸는 데 필요한 마법석 개수의 최솟값을 구하시오.
입력
입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.
X
Y
A
E
S
R
X, Y 는 영소문자만으로 이루어진 서로 다른 문자열이며, 둘 다 길이는 1 이상 100 이하이다. A, E, S, R 은 모두 1 이상 106 이하인 정수이다.
입력의 끝은 '#' 하나만으로 이루어진 줄로 나타낸다. 입력에 포함되는 데이터 세트의 수는 최대 50개이다.
출력
각 데이터 세트마다 문자열 X 를 문자열 Y 로 바꾸는 데 필요한 마법석 개수의 최솟값을 한 줄에 출력하시오.